首页 > 代码库 > USACO 3.2 kimbits DP
USACO 3.2 kimbits DP
自己YY了个DP:设f[n][l]为n位数中包含不超过l个1的总个数
f[n][l]=f[n-1][l]+f[n-1][l-1]
然后用_search()从高位向低位扫描即可,tmp记录当前已记下多少个数了(这些数肯定都比第I个小)
一开始f数组的初值YY错了,看了nocow改过来就好了
1 /* 2 PROB:kimbits 3 LANG:C++ 4 */ 5 #include <stdio.h> 6 #include <cstring> 7 int N,L,tmp; 8 long long I; 9 int a[1000];10 int f[1000][1000];11 12 void _search(int n,int l)13 {14 if ((n<=0)||(l<=0)) return;15 int t1=f[n-1][l],t2=f[n-1][l-1];16 if (tmp+t1>=I)17 {18 a[n]=0;19 _search(n-1,l);20 }21 else22 {23 tmp=tmp+t1;24 a[n]=1;25 _search(n-1,l-1);26 }27 }28 29 int main()30 {31 freopen("kimbits.in","r",stdin);32 freopen("kimbits.out","w",stdout);33 34 scanf("%d%d%lld",&N,&L,&I);35 36 memset(f,0,sizeof(f));37 for (int i=0;i<=N;i++)38 {39 f[i][0]=1;40 f[0][i]=1;41 }42 43 for (int i=1;i<=N;i++)44 for (int j=1;j<=L;j++)45 if (j>i)46 f[i][j]=f[i][i];47 else48 f[i][j]=f[i-1][j]+f[i-1][j-1];49 // XXXXX = 0XXXX + 1XXXX50 /*51 for (int i=1;i<=N;i++)52 {53 for (int j=1;j<=N;j++)54 printf("%d ",f[i][j]);55 printf("\n");56 }57 */58 tmp=0;59 _search(N,L);60 61 for (int i=N;i>=1;i--)62 printf("%d",a[i]);63 printf("\n");64 65 return 0;66 }
USACO 3.2 kimbits DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。