【USACO 3.2】Stringsobits （dp）
题意：求第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[40][40],k;
int main(){
freopen("kimbits.in","r",stdin);
freopen("kimbits.out","w",stdout);
scanf("%d%d%lld",&n,&l,&k);
for(int i=0;i<=n;i++)dp[0][i]=1;
for(int i=1;i<=n;i++){
dp[i][0]=1;
for(int j=1;j<=l;j++)
dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
}
for(int i=1;i<=n;i++)
if(dp[n-i][l]>=k)printf("0");
else{
printf("1");
k-=dp[n-i][l];
l--;
}
puts("");
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-11-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读