本文共 1455 字，大约阅读时间需要 4 分钟。
注意点：
time=1：活动范围为4-6；
time=2：3-7；
time=3：2-8；
time=4：1-9；
time=5：0-10（全范围）
突破口：
状态：dp[i,j]在i秒，j位置能获得的最大饼数
状态转移方程：
dp[i,j]=max(dp[i-1,j],dp[i-1,j-1],dp[i-1,j+1])；
此题涉及到一些代码技巧，要多注意。
代码如下：
#include #include #include using namespace std;int dp[100001][11],a[11]; //a[i]为辅助数组，记录某一时刻，i位置饼的数量struct bing{ int p; int t;}b[100001];bool cmp(bing x,bing y) //按掉落时间从小到大排序{ if(x.t!=y.t) return x.t n-1) //k>n-1了，此时一定要结束循环了，否则会报错！！！！！ break; } }//printf("%d %d\n",dp[Time][5],dp[0][5]); if(step==1) for(j=4;j<=6;j++) dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i-1][j+1]))+a[j]; else if(step==2) for(j=3;j<=7;j++) dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i-1][j+1]))+a[j]; else if(step==3) for(j=2;j<=8;j++) dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i-1][j+1]))+a[j]; else if(step==4) for(j=1;j<=9;j++) dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i-1][j+1]))+a[j]; else for(j=0;j<=10;j++) if(j==0) dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+a[j]; else if(j==10) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[j]; else dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j],dp[i-1][j+1]))+a[j]; // printf("%d %d\n",dp[Time][5],dp[0][5]); } for(i=0;i<=10;i++) if(dp[Time][i]>=ans) ans=dp[Time][i]; printf("%d\n",ans); } return 0;}
补充：其实这道题也可以像数塔一样做，后面有空试着A一下。
转载地址：http://bbdci.baihongyu.com/