首页 > 代码库 > SPOJ GNYR09F 数字上的找规律DP
SPOJ GNYR09F 数字上的找规律DP
Problem C SPOJ GNYR09F
dp题,dp可能刚刚开始对大家来说比较难,但是静下心来分析还是比较简单的;
dp(i ,j ,k)表示前i个数中,当前累积和为j,末尾数字为k的方案数。
考虑第i个位置的2种情况:
1.放0:dp(i,j,0) = dp(i-1,j,0) + dp(i-1,j,1)
2.放1:dp(i,j,1)= dp(i-1,j,0)
因为每一行最开始的状态均从i=j+1,dp(i,j,0)=0,dp(i,j,1)=1开始的,但因为这样子开头均为1,那些除此之外的情况的要从上一层算下来就是
dp(i,j,1) += dp(i-1,j-1,1)
如果还有j>=1,dp(i,j,1) += dp(i-1,j-1,1)
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 #define N 101 5 int dp[N][N][2]; 6 int main() 7 { 8 int T,a,b,c; 9 scanf("%d",&T);10 while(T--){11 scanf("%d%d%d",&a,&b,&c);12 memset(dp,0,sizeof(dp));13 dp[1][0][0]=1,dp[1][0][1]=1;14 for(int i=0;i<=c;i++) dp[i+1][i][1]=1;15 for(int i=0;i<=c;i++){16 for(int j=i+2;j<=b;j++){17 dp[j][i][0]=dp[j-1][i][0]+dp[j-1][i][1];18 dp[j][i][1]=dp[j-1][i][0];19 if(i>=1) dp[j][i][1]+=dp[j-1][i-1][1];20 }21 }22 printf("%d %d\n",a,dp[b][c][0]+dp[b][c][1]);23 }24 return 0;25 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。