【来源】:
2008年哈尔滨区域赛题目
【题目链接】:
http://acm.hdu.edu.cn/showproblem.php?pid=2452
【参考博客】:
https://blog.csdn.net/watermuch/article/details/9465185
【题意】:
真的要好好检讨,英语不好,这个题就别想做了。
意译一波,就是船是有两位领导 进行领航,一位叫做V,另一位叫G。
给出一幅有向无环图,每一个节点都有一个权值,如果经过这个节点都会获得对应的权值。
从一个入度为0的节点开始,到某个出度为0的节点停止。
但是两个人的想法不同:
V想要权值和尽可能大,G想要权值和尽可能小。
最后问,给出一个F,如果在一波操作之后获得的权值和大于等于F则”V胜利“,否则就”G荣誉“。
【题解】:
在图上跑DAG最长路,边记录对应的dp值,边跑,如果当前领航的人是谁,就分别写出对应的走法。
一定需要记忆化搜索,主要是因为多个起点,记忆化尽可能减少复杂度。
【代码】:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+; vector<int>G[N];
int dp[N][],w[N],du[N];
int n,m,f; /*
多组输入,记住要清空
*/
void Init(){
for(int i=;i<=n;i++){
du[i] = dp[i][] = dp[i][] = ;
G[i].clear();
}
}
/*
DAG记忆化搜索
dp[i][1/0]
对于第i个节点来说:
[1]——V在领航,他想要权值最大化。
[0]——G在领航,他想要权值最小化。 */ int dfs(int u,int cur){ cur %= ;
if( dp[u][cur] ) return dp[u][cur]; int Size = G[u].size() ;
if( Size == ) return w[u] ; int maxz = - , minz = 0x3f3f3f3f;
for(int i=;i<Size;i++){
int to = G[u][i];
/*
请注意V,G交替领航,当前位置来说,下一个点是最大化还是最小化、
1——Max
0——Min
*/
if( cur ){
maxz = max( maxz , dfs(to,cur+) ) ;
}else{
minz = min( minz , dfs(to,cur+) ) ;
}
} /*
但是过程中的节点的权值都会被记录并返回到上面的for里面。 */
if( cur ) return dp[u][cur] = maxz + w[u] ;
else return dp[u][cur] = minz + w[u] ;
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&f)){
Init();
for(int i=;i<=n;i++) scanf("%d",&w[i]);
for(int i=,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);
du[v] ++ ;
}
/*
∵V先手领航
∴他的目标就是让自己的值最大化,使其大于等于f.
*/
int maxz = - ;
for(int i=;i<=n;i++){
//题目要求要从入度为0的节点开始.
if( !du[i] ){
maxz = max( maxz , dfs(i,) ) ;
}
}
if( maxz >= f ) puts("Victory");
else puts("Glory");
}
return ;
}