首页 > 代码库 > USACO 3.2 kimbits DP

USACO 3.2 kimbits DP

2024-07-27 14:05:30   220人阅读

自己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 }
View Code

 

USACO 3.2 kimbits DP


联系
我们