(hdu2452)

题目描述

In times of peace, various countries have held regular maneuvers to maintain military’s vigilance. There is a navy fleet in a certain country which also starts a new round imaginary naval battle.

At the maneuver stage, the admiral intends to assess the combat effectiveness of two warships, “Victory” and “Glory”, so he lets two warships carry out countering exercises. Both of the warship commanders are young and promising, who graduated from naval academy as outstanding students. Not only have they had rich navigation direction experiences, but also have profound scientific knowledge, especially in mathematics. 

The admiral appoints one marine area dotted with many islets. Suppose all these islets are occupied by the enemy, and there are positive integers of enemy firebases. The hypothetical exercise situations given by the admiral and the rule of the competition are as follows:

(1) All the occupied islets are connected. There are some routes among these islets, but the route from one islet to another islet is unidirectional. In other words, if we take an islet as a node and an islet route as an edge, then we will get a directed non-cyclic connected graph.
(2) There is a unique 1st islet in the graph. If we start from this islet, we can reach any other islet. （maybe the 1st islet is not the islet which is numbered 1）
(3) At the beginning of the maneuver, two warships simultaneously sail to the 1st islets and eliminate all enemy firebases together.  
(4) The two warships, “Victory” and “Glory” take turns to navigate and exchange as soon as they arrive at an islet, then they move forward together. But each time they can only go along the unidirectional route, sail to the islet directly connected to the current, and eliminates all the enemy firebases on the islet. By the way, when start from 1st islet, “Victory” first navigates.
(5) Because each route is unidirectional, and graph is non-cycle, therefore the maneuver terminates when the two warships fail to go on navigating.
(6)When the maneuver ends, sum the numbers of eliminated enemy firebases on the routing path. If the number is greater than or equal to certain number f assigned by the admiral, then “Victory” wins. Otherwise, “Glory” wins.

The warship commanders are both mathematicians. After being assigned to such task, they see it is a Graph Theory problem. On the first simple directed non-cyclic connected graph, each node has a certain positive integer,it indicates the enemy firebases. The assignment is that two captains take turn to move forward along the directed edge until they are unable to do so. Then sum the total positive integers of the nodes on the routing path. Compare the number with the certain number f, and decides the final winning or losses.

Therefore, when it is the time for their own navigation, they are supposed to choose the route to win the final success.

 

 

输入

There are several test cases, in each case there are three positive integers n, m and f in first line. n indicates there are n (1< n <10000 ) nodes in the graph. The node serial number is arranged from 1 to n. m indicates that there are m edges in the graph. The following line has n positive integers, which indicate in sequence the positive integers in the nodes. Finally, there are m lines, and each line has two positive integers a, b (1< = a, b< =n), indicating there is a directed edge from the a node to the b node. Input is terminated by the end of file.

 

输出

To each group of the test case, if “Victory” wins, then output “Victory”. Otherwise, output “Glory”. The output each case takes up one line.

 

样例输入

复制样例数据

4 4 7
2 2 2 2
4 2
2 1
4 3
3 1
4 5 6
1 2 3 4
1 2
1 3
1 4
2 3
4 3

样例输出

Glory
Victory

题目大意:这个题目的题面也是高等英语水平才能读懂叭..,大体意思就是 给出一些岛屿这些岛屿之间有几条单向的道路,两艘船首先同时到达一个岛屿,随后A船先领航去一个岛屿,之后B船再领航去另外一个岛屿,这样轮流领航一直到,不能走了为止(无路),其中路径上的点都有权值,该条路径的权值就是路径上点的权值之和,然后如果 路径上的权值大于输入的f,则A船胜利,否则 B船胜利.问谁胜利.

题目思路:

首先我要分享一下,我的第一个思路,A*启发式搜索,从结束点倒着跑 spfa,结果队友一下就给推翻了...

这题类似于博弈,又不是博弈,首先弄明白一个事情 A船绝对想获得更多的权值,B船绝对想获得少的权值.

我们对每个点进行分析,这个点要么是通过 A领航来的,要么是通过B领航来的,所以我们用一个dp数组来储存每一个点的状态:

dp[v][1] 到达当前节点 是由 A船领航过来的,或者是由B船领航过来的,所以:

dp[v][1]=max(dp[v][1],dp[u][0]+num[v])// u - > v 有边,如果由A船领过来,那么他之前的点就是 B船领的 

dp[v][0]=min(dp[v][0],dp[u][1]+num[v])  // 反之依然成立.

然后我们就可以分奇数步,偶数步,对这个图进行深搜,不过还是T掉了,图太大,基本上是可以T的,我们想一下为什么,看下图:

我们不单纯看这张图现在,我们C->B加一条边 ,由C->B的边,这样我们再去深搜的时候很明显又把B的子树重新搜了一遍,所以我们考虑,能不能把B这个节点的最优值确定,这样我们直接return掉就可以了,答案肯定是可以得了.既然正着麻烦,我们把dp数组倒过来,现在dp数组表示.dp[i][1]表示,我们从当前节点i出发,由A船领航获得的最大值,那么首先有一个末状态我们可以确定:如果这个点是终点那么 dp[i][0]=dp[i][1]=num[i] 该节点的权值(因为它没路可走谁领都是当前权值),假设我们到了 D节点左儿子节点,这个点状态标记好之后,dp[D][1]=max(dp[#][0]+num[D],dp[D][1])// 这样我们就算出了,到达D节点如果A先走的最优值,B先走的最小值,所以我们再访问到这个节点的时候,我们直接利用这个值就可以了.这个实现需要靠回溯,确定儿子的最优状态就可以确定父亲的最优状态.然后我们再 由C->B时我们就可以直接利用 B点的最优状态 dp[C][1]=max(dp[D][0]+num[C],dp[C][1]) 就可以了,这样我们就省去了很多时间,也没必要分奇数步和偶数步讨论.

具体代码如下:

#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef  long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=998244353;
ll n,m,f;
int in[10005],ou[10005];
ll num[10005];
int head[maxn];
ll dp[10005][2];
ll cnt=0;
struct node{
    int e,next;
}edge[maxn];
void addedge(int u,int v)
{
    edge[cnt].e=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void restart()
{
    cnt=0;
    for(int i=1;i<=2*m;i++) head[i]=-1;
    for(int i=1;i<=n;i++)
    {
        dp[i][1]=dp[i][0]=-1;
        in[i]=ou[i]=0;
    }
}
void dfs(int u)
{
    if(dp[u][1]!=-1 || dp[u][0]!=-1) return;
    if(ou[u]==0)
    {
        dp[u][1]=dp[u][0]=num[u];
        return;
    }
    dp[u][1]=-INF;// keep max,first move
    dp[u][0]=INF;//keep min
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int e=edge[i].e;
        dfs(e);
        dp[u][1]=max(dp[u][1],dp[e][0]+num[u]);
        dp[u][0]=min(dp[u][0],dp[e][1]+num[u]);
    }
}
int main()
{
    while(~scanf("%lld%lld%lld",&n,&m,&f))
    {
        restart();
        for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
        for(int i=1;i<=m;i++)
        {
            int x,y;scanf("%d%d",&x,&y);
            addedge(x,y);++ou[x];++in[y];
        }
        int root;
        for(int i=1;i<=n;i++) if(in[i]==0){root=i;break;}
        dfs(root);
        if(dp[root][1]>=f) printf("Victory\n");
        else printf("Glory\n");
    }
    return 0;
}

总结:第一次做到这种图上DP与记忆化搜索的结合,如果以后再遇到对于某个点有有限个状态的时候(A领航,B领航)而且可以确定最优状态时,应该往记忆化搜索考虑!