首页 > 代码库 > 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;
}