1.分析
这道题目做法有很多，作为一个初学者，还是用深搜来解答。上课老师提示过有两个剪枝条件
最小价格没有改变则退出最大利润没有改变则退出
所以在写深搜的时候，需要记录一下最小价格和最大利润。
洛谷的题解第一名采取了深搜加动态规划的方式，他的DP思路和我们老师上课提示过的很相似。只不过他的代码中，记录最大利润的数组、记录最小价格的数组都可以被优化掉 ，虽然算法题不需要考虑空间复杂度。
2.AC代码
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <stdio.h>
#include<vector>
using namespace std;
#define MAX 1000000
int n,m;
vector<int> g[100001];
int profit[100001];// 到 第i个城市时的最大利润
int Price[100001];
int minPri;
void dfs(int now,int pre,int min_price)
{
int flag=1;
// min_price=min(min_price,Price[now]);
if(min_price>Price[now])
{
flag=0;
min_price=Price[now];
}
int a=max(profit[pre],Price[now]-min_price);
if(a>profit[now])
{
flag=0;
profit[now]=a;
}
if(flag) return;
for (int i = 0; i < g[now].size(); i++)
{
dfs(g[now][i],now,min_price);
}
}
int main()
{ int a;
int i;
int x,y;
scanf("%d %d",&n,&m);
for ( i = 1; i <= n; i++)
{
scanf("%d",&Price[i]);
}
for ( i = 1; i <= m; i++)
{
scanf("%d %d %d",&x,&y,&a);
g[x].push_back(y);
if(a==2)
{
g[y].push_back(x);
}
}
dfs(1,0,MAX);
cout<<profit[n]<<endl;
}
我这里的代码并没有优化掉记录最大值的数组。如果保留了这个最大值的数组，就更有动态规划的感觉了。
3.反思
这道题目关键是如何剪枝/DP。
因为售出价格可能在将来出现，所以我们总是希望购入价格尽可能地小。所以当最小价格没有更好的改进的时候，这个点就没有那么好了。其次，如果购入价格没有变的更低的话，我们需要考虑利润了。如果利润更好，说明这个点是有进一步深搜的价值的。感觉像是以是否在当前城市卖出为分界。
如果在当前城市卖出，那么说明在当前城市所获得的利润，比之前的利润都要高。可以记录一下当前城市所获得的利润，然后继续向下深搜，看有没有更好的利润。如果不在当前城市卖出，说明最低价格更新了，我们可以向下面的城市看看有无更高的价格让我们出售。
