CodeForces 14E Camels ：利用1-4拼成长为n的序列，使准确含有t个峰t-1个谷，求方案数 ：dp...

3 ≤ n ≤ 20, 1 ≤ t ≤ 10

如此小的数据接下来就能各种暴力了===

dp[i][j][k][t1][t2]表示前i个字符的最后两个是j和k已有t1个峰t2个谷

枚举当前放的数，转移方程容易思考了=

复杂度是20*4*4*10*10*4==轻松过啊

1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 int dp[21][5][5][11][11]; 6 int main() 7 { 8 int ans,n,t,i,j,k,x,y,l; 9 scanf("%d%d",&n,&t); 10 memset(dp,0,sizeof(dp)); 11 for (i=1;i<=4;i++) 12 for (j=1;j<=4;j++) dp[2][i][j][0][0]=i!=j; 13 for (i=3;i<=n;i++) 14 for (j=1;j<=4;j++) 15 for (k=1;k<=4;k++) 16 for (x=0;x<=t;x++) 17 for (y=0;y<=t;y++) 18 for (l=1;l<=4;l++) 19 if (k!=l) 20 dp[i][k][l][x+(j<k&&k>l)][y+(j>k&&k<l)]+=dp[i-1][j][k][x][y]; 21 ans=0; 22 for (i=1;i<=4;i++) 23 for (j=1;j<=4;j++) ans+=dp[n][i][j][t][t-1]; 24 printf("%d\n",ans); 25 return 0; 26 } View Code

题目链接：http://codeforces.com/problemset/problem/14/E

转载于:https://www.cnblogs.com/xiao-xin/articles/4370479.html

总结

以上是生活随笔为你收集整理的CodeForces 14E Camels ：利用1-4拼成长为n的序列，使准确含有t个峰t-1个谷，求方案数 ：dp...的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。