首页 > 代码库 > nefu 642 monkey
nefu 642 monkey
题目:大意是说 有n个台子,编号1-n,开始时,有一只猴子站在编号1的台子上,猴子可以自由地蹦到两侧的台子上,每次i移动话费的时间是一秒,有个人每秒钟仍一个盘子到其中的一个台子上,问在猴子移动次数不超过t的情况下,猴子能接到的最多的盘子数。
方法:一个dp的题目,原来看到过,还不会做,直到最近在做dp的题目,才解决了这个题目。
使用一个三维数组dp[i][j][k],i代表当前进行到第i秒钟,也是第i盘子扔出的时间,j代表当前移动的步数,k代表当前所处的台子编号。
很容易能找到状态转移方程:dp[i][j][k]=max(dp[i-1][j][k],max(dp[i-1][j-1][k-1]),dp[i-1][j-1][k+1])+(f[i]==k);
当然本题的f[i]是有相应的值的,需要在进行一下处理。
已经找到了状态转移方程之后,还有一些要注意的问题就是需要进行一下限制,比如:题目中已经说到了猴子的初始位置是一号台子,而不是随意的,所以这里就需要注意了,当进行到第i个盘子的时候,假设j>i,从一开始到此时猴子的移动范围为1-i+1这几个台子,所以要加一个限制条件了,因为这个错了n次。
代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; struct node { int d,v; }z[105]; int dp[105][105][105]; int main() { int n,m,t,sum=1; int i,j,k; while(scanf("%d%d%d",&n,&m,&t)!=EOF) { int mas=0; memset(dp,0,sizeof(dp)); for(i=1;i<=m;i++) scanf("%d%d",&z[i].d,&z[i].v); t++; for(i=1;i<=m;i++) for(j=1;j<=t&&j<=i+1;j++) //这里加了限制,还有为了方便dp数组中j-1不使得数组越界,我把移动次数用1代表0,2代表1...这也是为什么上面t++ for(k=1;k<=n&&k<=j;k++) //k>j就没必要更新了 { dp[i][j][k]=max(dp[i-1][j][k],max(dp[i-1][j-1][k-1],dp[i-1][j-1][k+1])); if(z[i].d==k) dp[i][j][k]+=z[i].v; if(mas<dp[i][j][k]) mas=dp[i][j][k]; } cout<<"Scenario #"<<sum++<<endl; cout<<mas<<endl<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。