题解 P2991 【[USACO10OPEN]水滑梯Water Slides】

· · 题解

本人表示一开始看到这道题的时候并没有看懂

比如这句

如果Bessie选择了在最坏情况下，最大化她的开心值，那么，她在这种情况下一次冲浪可以得到的最大开心值是多少？

机房大佬给出的解答是:

假设你有意想让Bessie的愉悦值最小,题目规定你只能改k条边,在你们双方都做出最优决策的情况下,所能得到的愉悦值是多少?

我想这不是博弈论吗(惊吓)

其实并不是很复杂

双方最优的意思大概就是:如果其中一方的操作不符合这个步骤,那么另一方总可以通过一些步骤,使得结果更加偏向自己的一方

似乎有种命中注定的感觉

接下来开始解题吧

状态设为f[k][i](0≤k≤K),

表示Bessie从i号节点出发,在k次失误下能够得到的最优值

因为Bessie一定会冲到n号节点,所以我们以f[0][n]=0作为开始状态

考虑f[k][i]的转移,当前只可能有两种决策:

1.Bessie选择最优决策:此时它应该是从f[k][v](v为以u开始的边指向的结点)中选择一个最大值,然后选择那个方向;如果它不选择那个方向的话,我们就可以通过之后的k次修改使得它达不到比当前更大的愉悦值;即a=max({f[k][v]})

2.我们选择最优决策(即让Bessie走向愉悦值最小的道路),那么我们肯定会从

f[k-1]v中选择一个最小值,然后让Bessie走上那条不归路...即if(k>0)b=min({f[k-1][v]})

这两种决策的结果应该取最小值,因为我们可以选择从什么时候让BEssis滑稽w

f[k][u]=min(a,b)

最后答案在f[K][1]

最后注意开long long

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define RG register
using namespace std;
typedef long long ll;
const int N=50010;
const int M=150010;
const ll inf=((1ll*1)<<60);
ll n,m,k;
ll head[N],to[M],nxt[M],val[M],cnt;
ll f[11][N];
ll d[N],x[N];
bool vis[N];
queue<ll>Q;
inline void add(ll u,ll v,ll w){
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

ll dfs_memory(ll u,ll s){//记忆化搜索(正推公式太过复杂)
    if(u==n)return 0;
    if(f[s][u])return f[s][u];
    RG ll maxn=0,minn=inf,v;
    for(RG int i=head[u];i;i=nxt[i]){//第一种情况
        v=to[i];
        maxn=max(maxn,dfs_memory(v,s)+val[i]);
    }
    if(s)
        for(RG int i=head[u];i;i=nxt[i]){//第二种情况
            v=to[i];
            minn=min(minn,dfs_memory(v,s-1)+val[i]);
        }
    if(!s)f[s][u]=maxn;
    else f[s][u]=min(maxn,minn);
    //printf("f[%d][%d]=%d\n",s,u,f[s][u]);
    return f[s][u];
}

int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for(RG ll i=1,u,v,w;i<=m;i++){
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
    }
    printf("%lld\n",dfs_memory(1,k));
    return 0;
}