Adjacent Bit Counts(01组合数)
Adjacent Bit Counts 4557 Adjacent Bit Counts 题意:给你一个长为n的串,且仅有0和1组成,x 1 ? x 2 + x 2 ? x 3 + x 3 ? x 4 + . . . + x n?1 ? x n 这样计算的值等于k,问该字符串有多少种这样的组合? 分析:用动态规划的思想,假如dp[i][j][k]表示组合数,i表示字串长度,j表示该串价值,k表示最后一个字符只能为1和0。 dp[i][j][0],有i个字符,价值为j,最后一位为0,这样的组合数等于长度为i-1,价值为j,最后一位为0的组合数加上长度为i-1,价值为j,最后一位为1的组合数,即dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1]。 dp[i][j][1],最后一位为1,这样的组合数等于长度为i-1,价值为j,最后一位为0的组合数加上长度为i-1,价值为j-1,最后一位为1的组合数,即dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j-1][1]。 总结下来状态转移方程即是: dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1] dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j-1][1] 再说说初始化 长度为1的时候,没有其他的数和它相乘,所以价值只能为0 dp[1][0][0]=1;长度为1价值为0且最后一位为0的组合数只有1种,比如0 dp[1][0][1]=1;长度为1价值为0且最后一位为1的组合数只有1种,比如1 看了别人题解,都说这是很简单的动规,佩服佩服 ? 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int dp[105][105][2];//dp定义为全局变量 5 void find_(){ 6 dp[1][0][0]=dp[1][0][1]=1;//初始化 7 for(int i=2;i<105;i++){//每一个长度时,都需要初始化一遍 8 dp[i][0][0]=dp[i-1][0][1]+dp[i-1][0][0]; 9 dp[i][0][1]=dp[i-1][0][0]; 10 for(int j=1;j<i;j++){//长度为i时,价值最多为i-1 11 dp[i][j][0]=dp[i-1][j][1]+dp[i-1][j][0]; 12 dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j-1][1]; 13 } 14 } 15 } 16 int main() { 17 int p; 18 find_(); 19 scanf("%d",&p); 20 while(p--) { 21 int n,a,b; 22 scanf("%d %d %d",&n,&a,&b); 23 printf("%d %dn",n,dp[a][b][0]+dp[a][b][1]); 24 } 25 return 0; 26 } 27 28 CUTECode (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |