题解-猴子吃香蕉

· · 个人记录

【问题描述】

　　一只猴子找到了很多香蕉树，这些香蕉树都种在同一直线上，而猴子则在这排香蕉树的第一棵树上。这只猴子当然想吃尽量多的香蕉，但它又不想在地上走，只想从一棵树跳到另一棵树上.同时猴子的体力有限，它不能一次跳得太远或跳得次数太多，每当他跳到一棵树上，就会把那棵树上的香蕉都吃掉。那么，它最多能吃多少个香蕉呢？

【输入格式】

　　输入第一行为三个整数，分别是香蕉树的棵数N,猴子每次跳跃的最大距离D，最多跳跃次数M.

　　下面N行每行包括两个整数，ai,bi分别表示每棵香蕉树上的香蕉数，以及这棵树到猴子所在树的距离。输入保证这些树按照从近到远排列，并且没有两棵树在同一位置。b0总是为0 .

【输出格式】

输出只有一行，包含一个整数，为猴子最多能吃到的香蕉数。

【输入样例】

5 5 2

6 0

8 3

4 5

6 7

9 10

【输出样例】

20

思路

//分析:原始状态是在第一棵树走了0步，得到香蕉a[1]个。

//接着可以表示dp[i][j]表示在第i棵树上，此时走了第j步。那么这个状态往后怎么推呢？考虑此时状态，若跳到这里，那就是dp[k][j-1]+a[i];j-1代表前面的j-1次跳跃,k代表可以从哪一颗树上跳过来，但此时要满足b[i]-b[k]<=d;

Ac code:

#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans,maxx,a[10005],b[10005],dp[10005][10005];
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=105;i++)
    for(int j=0;j<=105;j++)
    dp[i][j]=-1111;//注意既然要最小就尽量小 
    dp[1][0]=a[1];//初始状态 
    maxx=a[1];//注意maxx要赋初值 
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=k;j++)//j枚举跳的步数 
        {
            for(int l=1;l<i;l++)
            {
                if(b[i]-b[l]<=m)//验证 
                {
                    dp[i][j]=max(dp[i][j],dp[l][j-1]+a[i]);//dp转移方程 
                    maxx=max(maxx,dp[i][j]);//更新答案 
                }
            }
        }
    }
    cout<<maxx;
    return 0;
}