题解 P1073 【最优贸易】

· · 题解

来一篇DP解法

经典DP模板都是

for(int i=1;i<=n;i++)
{
    f[i][j]=max / min (状态转移方程)
    f[状态]=最优解

}

ans=f[最终状态]；

我们可以发现，dp实际上就是把大问题化为小问题，通过寻找（for循环）小问题的最优解/枚举各个状态的最优解，递推得到大问题的最优解，而实现寻找的工具，无非就是搜索

所以，我们可以用搜索代替for循环，一步一步寻找/递推问题的多种状态/可能解/小问题最优解，最后解决问题。

搜索+DP的基本结构，只是把for循环换成DFS/BFS而已。我们可以吧需要记录的状态，暂时解等用数组或递归程序的形参保存，需要时用IF判断

当然这用方法的难点和DP是一样的，思考怎样递推大问题/寻找什么状态/小问题是什么才是精髓

回到本题，分析后我们知道，阿龙每次来到一个点，他应该关心3个问题：

1.我在哪（废话）

2.这个城市物价如何

3.若我在曾经经过的城市买水晶球，在这里卖了，我能赚最多钱吗？

显然了！前两个问题你可以十分确定的告诉他，但第三个问题是不确定的。所以我们的搜索+DP将要讨论的就是这个问题

初步的思路：我们可以设f[i]为在i城时，阿龙曾经经过的城市中物价最小值。但是！我们去i城的路线绝不可能只有一种，所以你要二维数组f[i][j]来记录第j种情况。可又但是！你并不知道j会有多大，这就导致你无法开数组；我们观察题目条件中，水晶球价格≤100。这样，我们可以用一种很巧的方法：

设bool数组f[i][j]表示在i城时，曾经经过的城市中物价最小值。

我们使用BFS进行搜索。当f[i][j]==1时，表示这种状态已经讨论过了，以这种状态往下的讨论只会有相同结果，不再加入BFS的队列。当f[i][j]==0时，再继续讨论这种状态在往后面走的新结果。这样，对于每个城市的可能性进行讨论，我们就能搜出问题的最优解了；

但还有一个问题，对于某些城市，可能进去之后阿龙就不能再走到终点n了，而他必须在n城结束旅行。我们需要预处理，把这些城市去掉，不纳入上面的讨论范围。我们可以把地图反向存一遍，然后以n城为起点反向搜索，此时无法到达的点，在正向时必定不能从那里到n城。

上码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int price[100001];
int next[500001],to[500001],x[500001];//正向构图
int next_re[500001],to_re[500001],x_re[500001];//反向构图
int n,m;
int queue[3000000];//反向BFS用单层队列够了
bool vis[100001];
bool f[100001][102];
int q[3000000][2];//正向BFS需要储存队列中元素的额外状态，用双层队列（本质就是两个数组）
int main()
{
std::ios::sync_with_stdio(false);//读入优化简单版
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>price[i];
int cnt=0;
int a,b,c;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
if(c==1)//双向构建边
{
    cnt++;
    to[cnt]=b;
    next[cnt]=x[a];
    x[a]=cnt;//正

    to_re[cnt]=a;
    next_re[cnt]=x_re[b];
    x_re[b]=cnt;//反
}
else if(c==2)
{
    cnt++;
    to[cnt]=b;
    next[cnt]=x[a];
    x[a]=cnt;

    to_re[cnt]=a;
    next_re[cnt]=x_re[b];
    x_re[b]=cnt;

    //----------------------

    cnt++;
    to[cnt]=a;
    next[cnt]=x[b];
    x[b]=cnt;

    to_re[cnt]=b;
    next_re[cnt]=x_re[a];
    x_re[a]=cnt;
}
}

//反向BFS
int h=1,t=1;
queue[1]=n;
vis[n]=1;//首元素进队
while(h<=t)//当队不空时
{
int k=queue[h];h++;//取头元素，出队
for(int j=x_re[k];j!=0;j=next_re[j])//遍历其出边
{
    if(vis[to_re[j]]==0)
    {
        vis[to_re[j]]=1;//vis存储是否访问过(等价于是否可以由终点访问)
        queue[++t]=to_re[j];//进队
    }

}
}

//正向BFS
h=1;t=1;
q[1][0]=1;
q[1][1]=price[1];//首元素进队
f[1][price[1]]=1;
int ans=-1;
while(h<=t)
{
int k=q[h][0];//双层队列
int mini=q[h][1];//[o]存点  [1]存该点对应状态的最小价值
h++;

//ans=std::max(ans,price[k]-mini);

ans=ans>price[k]-mini?ans:price[k]-mini;//先更新答案
for(int j=x[k];j!=0;j=next[j])
{
    if(vis[to[j]]==1)//若点可以到终点
    {
        int m=mini<price[to[j]]?mini:price[to[j]];//更新最小值
        if(f[to[j]][m]==0)//若这个状态没有被记录过
        {
            q[++t][0]=to[j];//该点进队
            q[t][1]=m;
            f[to[j]][m]=1;
        }
    }
}

}

cout<<ans;

return 0;
}

最后感谢神犇 SPiCa 的思路