洛谷P6759题解

· · 题解

本题是一道 DAG 上的 DP 题，了解 DAG 的可跳过第一章。

一、浅谈 DAG

DAG(Directed acyclic graph)，即 有向无环图（学过拓扑排序的应该知道，只有它才能进行拓扑排序）。如想了解更多信息，请自行查找资料，这里不再赘述。

二、解析样例数据

样例数据可以这么看：

4
13 9 19 3
0 10 20 3
4 0 11 2
1 15 0 12
5 5 13 0

这样，把图画出来就简单多了（由于线路复杂，画得不好请原谅）。

三、思路

这题可以用动态规划。

我们设 d_i 为从摊位 i 出发可以获得的最多礼物数量，p_i 为摊位 i 发放礼物的时间，t_{i,j} 为摊位 i 到摊位 j 所花时间。

如果 p_j-p_i \ge t_{i,j}，那么领完摊位 i 的礼物后还能领摊位 j 的礼物，即 i 到 j 存在边。由于时间为线性，建模后为 DAG。于是，问题就转换成了求 DAG 上的最长路。

在 DAG 中，每个摊位都可能成为开始位置（从摊位 1 走到这个摊位），但不是每个，需要满足 p_i \ge t_{1,i}，即去了以后能领到礼物。

本题使用记忆化搜索（话说题解区似乎全都是递推），于是 d_i 记录搜索结果。

四、代码

#include <bits/stdc++.h>
using namespace std;
const int N=405;
int n,ans,t[N][N],p[N],d[N];
int dp(int i)//记忆化搜索
{
    if(d[i])return d[i];//搜过了
    d[i]=1;//至少能领1个
    for(int j=1;j<=n;j++)
        if(i!=j&&p[j]-p[i]>=t[i][j])d[i]=max(d[i],dp(j)+1);
    return d[i];
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>t[i][j];
    for(int i=1;i<=n;i++)
        if(p[i]>=t[1][i])ans=max(ans,dp(i));
    cout<<ans<<endl;
    return 0;
}

五、总结

注意，第三章建立 DAG 时，已经与第二章的那个图没有关系了。开始时，我就被那个迷惑了，其实跑 dp 时根本不需要那个图。