【记忆化搜索】Navy maneuvers

【来源】：

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值，边跑，如果当前领航的人是谁，就分别写出对应的走法。

一定需要记忆化搜索，主要是因为多个起点，记忆化尽可能减少复杂度。

【代码】：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e4+10;
 4 
 5 vector<int>G[N];
 6 int dp[N][2],w[N],du[N];
 7 int n,m,f;
 8 
 9 /*
10     多组输入，记住要清空
11 */
12 void Init(){
13     for(int i=0;i<=n;i++){
14         du[i] = dp[i][0] = dp[i][1] = 0 ;
15         G[i].clear();
16     }
17 }
18 /*
19     DAG记忆化搜索
20     dp[i][1/0]
21     对于第i个节点来说：
22     [1]——V在领航，他想要权值最大化。
23     [0]——G在领航，他想要权值最小化。
24 
25 */
26 
27 int dfs(int u,int cur){
28 
29     cur %= 2 ;
30     if( dp[u][cur] ) return dp[u][cur];
31 
32     int Size = G[u].size() ;
33     if( Size == 0 ) return w[u] ;
34 
35     int maxz = -1 , minz = 0x3f3f3f3f;
36     for(int i=0;i<Size;i++){
37         int to = G[u][i];
38         /*
39             请注意V,G交替领航，当前位置来说，下一个点是最大化还是最小化、
40             1——Max
41             0——Min
42         */
43         if( cur ){
44             maxz = max( maxz , dfs(to,cur+1) ) ;
45         }else{
46             minz = min( minz , dfs(to,cur+1) ) ;
47         }
48     }
49 
50     /*
51         但是过程中的节点的权值都会被记录并返回到上面的for里面。
52         
53     */
54     if( cur ) return dp[u][cur] = maxz + w[u] ;
55     else return dp[u][cur] = minz + w[u] ;
56 }
57 int main()
58 {
59     while(~scanf("%d%d%d",&n,&m,&f)){
60         Init();
61         for(int i=1;i<=n;i++) scanf("%d",&w[i]);
62         for(int i=1,u,v;i<=m;i++){
63             scanf("%d%d",&u,&v);
64             G[u].push_back(v);
65             du[v] ++ ;
66         }
67         /*
68             ∵V先手领航
69             ∴他的目标就是让自己的值最大化，使其大于等于f.
70         */
71         int maxz = -1 ;
72         for(int i=1;i<=n;i++){
73             //题目要求要从入度为0的节点开始.
74             if( !du[i] ){
75                 maxz = max( maxz , dfs(i,1) ) ;
76             }
77         }
78         if( maxz >= f ) puts("Victory");
79         else    puts("Glory");
80     }
81     return 0;
82 }

View Code