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     else
22     {
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             else
48                 f[i][j]=f[i-1][j]+f[i-1][j-1];
49           // XXXXX =  0XXXX  +  1XXXX
50 /*
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("
");
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("
");
64 
65     return 0;
66 }

View Code