[Acwing] 341. 最优贸易 最短路||记搜

前言

传送门 :

记忆化搜索真的太难了吧,哈哈哈

建图 建不出来 思路都没有QAQ

DFS

考虑建图 : 因为我们有两个操作 , 一个是 买入，一个是卖出

所求答案为 a n s = m a x ( m a x ( s e l l ) − m i n ( b u y ) ) ans = max( max(sell) - min(buy)) ans=max(max(sell)−min(buy))

因此 我们需要维护两个值

所以我们可以 考虑建两个图 分别计算 买入和 卖出的最大值

(太牛了！！)

因此对于 计算 m a x ( s e l l ) 和 m i n ( b u y ) max(sell)和min(buy) max(sell)和min(buy) 我们可以用记忆化搜索,枚举每个点的所有

临点来解决

CODE

#include 
using namespace std;
const int N  = 1e5+10;
const int INF = 0x3f3f3f3f;
vector way_min[N],way_max[N];
int n,m;

int v[N],minn[N],maxn[N];

///v[i] 城市i的水晶球价格
///minn[i]  从1走到i 的过程
///maxn[i]  从i走到n中 卖出水晶球的最高价格

void dfs_min(int x,int m )
{
     if(m >= minn[x])
     return ;

     m =min(m,v[x]);
     minn[x] = m;

     for(auto i : way_min[x])
     {
        dfs_min(i,m);
     }
}

void dfs_max(int x,int m)
{
    if(m>n>>m;
    memset(minn,0x3f,sizeof minn);
    memset(maxn,-0x3f,sizeof maxn);

    for(int i=1;i>v[i];

    for(int i=1;i>a>>b>>c;

        ///这里表示求最小值所需的路径
        way_min[a].push_back(b);

        ///因为最大值是从n开始(从i到n可转化为从n到i)
        ///所以我们把所有路径倒个头
        way_max[b].push_back(a);


        if(c == 2)
        {
            way_min[b].push_back(a);
            ///这样子才可以互通
            
            way_max[a].push_back(b);
        }
    }
    dfs_min(1,v[1]);
    dfs_max(n,v[n]);

    int ans = -INF;
    for(int i=1;i