【USACO 3.2】Stringsobits (dp)

时间:2021-03-02 22:13:32

题意:求第k大的最多有l个1的n位二进制。

题解:dp[i][j]表示长度为i最多有j个1的二进制有多少种,则有:

状态转移:dp[i][j]=dp[i-1][j]+dp[i-1][j-1],即第i位放1或者0。

边界条件:dp[0][i]=1,dp[i][0]=1。

长度为n,最多m个1的二进制可以分为:

以0开始的一部分,共有dp[n-1][m]个,

和以1开始的一部分,共有dp[n-1][m-1]个。

如果dp[n-1][m]≥k,说明第k大的就在0开始的那一部分的第k大的,

否则就是1开始的那一部分的第k-dp[n-1][m]大的。

问题就转化为求长度n-1,最多m或m-1个1的二进制的第k或k-dp[n-1][m]大的是谁。

/*
TASK:kimbits
LANG:C++
*/
#include<cstdio>
int n,l;
long long dp[][],k;
int main(){
freopen("kimbits.in","r",stdin);
freopen("kimbits.out","w",stdout);
scanf("%d%d%lld",&n,&l,&k);
for(int i=;i<=n;i++)dp[][i]=;
for(int i=;i<=n;i++){
dp[i][]=;
for(int j=;j<=l;j++)
dp[i][j]=dp[i-][j]+dp[i-][j-];
}
for(int i=;i<=n;i++)
if(dp[n-i][l]>=k)printf("");
else{
printf("");
k-=dp[n-i][l];
l--;
}
puts("");
return ;
}