GDKOI 2009 猴子 题解

题目图

数据范围更正：M<N<=2000

这是蒟蒻C++学习机构自建（by Tsingdao OJ）的网站上的一道题，但题目来源是GDKOI 2009

题目大意

给定香蕉树数量N,每次跳跃最大距离D,最大跳跃次数M

以及N棵香蕉树的苹果数a[i]，离第一棵树的距离b[i]，保证b[1]=0

求出猴子跳跃最大所得香蕉数量，当然谁的输出<a[1]他就必然会被惩罚(doge)

题目分析

像这种多阶段多决策的最优值问题，就要用dp做。

养成画搜索树是好习惯，相当于用递归做了一遍，别管TLE，就拿样例去画。

/**
这里的输入是
5 5 2
6 0
8 3
4 5
6 7
9 10
输出是
20
*/

这里按跳跃次数划分阶段，决策是跳到哪一棵树上（好猴子不走回头路）

现在开始画树，阶段代表第几层，每个节点的(i,j,k)表示第i次跳跃跳到了第j棵树上，最大香蕉数量为k。

看完视频，我们画出了递归树

思考：有哪些状态可以合并，得到一个dp数组中的值呢？

目光看向第二层，2,4,20和2,4,16可以合并，取最大：20

为什么，层数必须分开，因为最后可以统一看最后一次跳跃方便。

所在树也要分开，否则没法判断距离是否合法。

于是这是二维问题，而所得的结果就是存在dp数组中的值。

dp[i][j]=k,前i次跳跃,到了j号树,最多k个香蕉。

如果想要知道前面那些香蕉树可以推出来，就要用一个x枚举j-1及之前的树，一旦遇到距离>D就停止，取max后加上a[j]即可。

得到方程

说得很清楚了，dp[i][j]，肯定要从dp[i-1][...]推出来，而这是上一步骤在的树编号，用x枚举，就像这样：

//Latex公式
//dp[i][j]=max\{dp[i-1][x]\}+a[j]\\ x\in[i,j-1]\\ b[j]-b[x]\le D

意思是，x从j-1往前枚举，只要b[j]-b[x]>d(即距离超限)则break，用遍历过的数取一个max，加上当前这棵树的香蕉树，就能得到dp[i][j]了！

另外，之所以枚举到i就行了，是因为第i-1次跳跃，最少跳跃到第i棵树上，因为每次都必须跳跃至少一棵树，一开始在第一棵树上，经过i-1次跳跃后，就到了第i棵树，因此从j-1枚举到i即可。

当然穷举j时，利用这一点，他的初值就是i+1，意味着第i次跳跃的最小树编号为i+1。

写出代码

快速看噢！

#include<bits/stdc++.h>
using namespace std;
int dp[2001][2001],a[2001],b[2001];
int main()
{
    int n,d,m;
    cin>>n>>d>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
    }
    dp[0][1]=a[1];
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            for(int x=j-1;x>=i && b[j]-b[x]<=d;x--)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][x]);
            }
            dp[i][j]+=a[j];
        }
    }
    int mx=-1;
    for(int i=1;i<=n;i++)mx=max(mx,dp[m][i]);
    cout<<mx;
}

亲测可以AC

古德白！