随笔-141  评论-9  文章-3  trackbacks-0
USACO 3.2.2 Stringsobits (DP)
DP

f[i][j] 表示长度为i 的01串，1的个数不多于j的个数。

则对于第i位是0还是1，可分为两个子状态 f[i][j]  =  f[i-1][[j] + f[i-1][j-1]

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

#include <fstream>

using namespace std;

long long N,L,I;
long long f[100][100];

int main(){

    int i,j;

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

    fin>>N>>L>>I;

    for(i=0; i<=N; ++i)
        f[0][i] = f[i][0] = 1;

    for(i=1; i<=N; ++i)
        for(j=1; j<=N; ++j)
            f[i][j] = f[i-1][j] + f[i-1][j-1];

    for(i=N; i>=1; --i)
        if(I>f[i-1][L]){
            fout<<"1";
            I -= f[i-1][L];
            --L;
        }else
            fout<<"0";

    fout<<endl;
    return 0;
}

posted on 2010-12-22 13:03 小阮 阅读(317) 评论(0)  编辑 收藏 引用 所属分类: USACO

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


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