随笔-141  评论-9  文章-3  trackbacks-0
USACO 4.4.1 Shuttle Puzzle (构造法求解)
一开始想到暴搜，但是状态太多，肯定TLE。

了USACO上给出构造法求解：

3

3 5 6 4 2 1 3 5 7 6 4 2 3 5 4

2 1 -2 -2 -1 2 2 2 -1 -2 -2 1 2 -1

4

4 6 7 5 3 2 4 6 8 9 7 5 3 1 2 4 6 8 7 5 3 4 6 5

2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1

5

5 7 8 6 4 3 5 7 9 10 8 6 4 2 1 3 5 7 9 11 10 8 6 4 2 3 5 7 9 8 6 4 5 7 6

2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 -1 2 2 2 2 2 -1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1

6

6 8 9 7 5 4 6 8 10 11 9 7 5 3 2 4 6 8 10 12 13 11 9 7 5 3 1 2 4 6 8 10 12 11 9 7 5 3 4 6 8 10 9 7 5 6 8 7

2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 -1 2 2 2 2 2 1 -2 -2 -2 -2 -2 -2 1 2 2 2 2 2 -1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1


规律很明显。

/*
ID: lorelei3
TASK: shuttle
LANG: C++
*/

#include <fstream>

using namespace std;

const int MAX = 500;

int n;
int two=2, one=1;
int a[MAX];

bool flag = true;

int main(){

    ifstream fin("shuttle.in");
    ofstream fout("shuttle.out");

    fin>>n;

    int loc=0, k=1;
    while(k!=0){

        if(k==n){
            flag=false;
            one = -one;
        }
        int t=k;
        while(t!=0){
            a[loc++] = two;
            t--;
        }
        a[loc++]=one;

        two = -two;
        one = -one;

        if(k<n && flag)
            k++;
        else 
            k--;
    }

    int res=n;
    fout<<n<<" ";

    for(int i=0, cnt=2; i<loc-1; ++i,++cnt){
        if(cnt==20){
            fout<<(res+=a[i])<<endl;
            cnt=0;
        }
        else
            fout<<(res+=a[i])<<" ";
    }
    
    res+=a[loc-1];
    fout<<res<<endl;

    return 0;
}
posted on 2011-01-30 22:11 小阮 阅读(373) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮