2010-1074

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by 猛犸也钻地

解题报告：

{{{
一道博弈题，题目说是个有向无环图，因此可以直接用记忆化做，不用考虑后效性了。

玩家要移动白旗和黑旗，自然在记录状态的数组中要有这两个，另外还要有当前的赌注，这会影响到决策，
用f[x][y][s+100]表示白旗在x点，黑旗在y点，当前赌注为s时的最多能赢的钱，s在[-100,100]内所以要+100。

记忆化搜索时，先把当前的f为-INF，如果有路可走，必然能更新到一个大于-INF的数，
把所有边都访问完了后发现f还是-INF，说明无路可走了，把f设成-s

另外，求出发路径数只要对起点连出的边看一遍就行了。
}}}


代码：

{{{
#!cpp
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int INF = 1000000;

vector<int> e[50];
int f[50][50][201],d[50];

int calc(int x, int y, int s){
    if(f[x][y][s+100]>-INF) return f[x][y][s+100];
    for(int i=0;i<e[x].size();i++){
        int v=-calc(e[x][i],y,s+d[e[x][i]]);
        if(v>f[x][y][s+100]) f[x][y][s+100]=v;
    }
    for(int i=0;i<e[y].size();i++){
        int v=-calc(x,e[y][i],s-d[e[y][i]]);
        if(v>f[x][y][s+100]) f[x][y][s+100]=v;
    }
    if(f[x][y][s+100]<=-INF) f[x][y][s+100]=-s;
    return f[x][y][s+100];
}

int main(){
    int n,m,x,y;
    while(scanf("%d%d%d%d",&n,&m,&x,&y)>0){
        memset(f,192,sizeof(f));
        for(int i=0;i<n;i++){
            scanf("%d",&d[i]);
            e[i]=vector<int>();
        }
        for(int i=0;i<m;i++){
            int p,q;
            scanf("%d%d",&p,&q);
            e[p].push_back(q);
        }
        printf("%d ",calc(x,y,1));
        int sum=0;
        for(int i=0;i<e[x].size();i++){
            int v=-calc(e[x][i],y,1+d[e[x][i]]);
            if(v==f[x][y][101]) sum++;
        }
        for(int i=0;i<e[y].size();i++){
            int v=-calc(x,e[y][i],1-d[e[y][i]]);
            if(v==f[x][y][101]) sum++;
        }
        if(!sum) sum=1;
        printf("%d\n",sum);
    }
}
}}}

by 猛犸也钻地

解题报告：

一道博弈题，题目说是个有向无环图，因此可以直接用记忆化做，不用考虑后效性了。
玩家要移动白旗和黑旗，自然在记录状态的数组中要有这两个，另外还要有当前的赌注，这会影响到决策，
用f[x][y][s+100]表示白旗在x点，黑旗在y点，当前赌注为s时的最多能赢的钱，s在[-100,100]内所以要+100。
记忆化搜索时，先把当前的f为-INF，如果有路可走，必然能更新到一个大于-INF的数，
把所有边都访问完了后发现f还是-INF，说明无路可走了，把f设成-s
另外，求出发路径数只要对起点连出的边看一遍就行了。

代码：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int INF = 1000000;
vector<int> e[50];
int f[50][50][201],d[50];
int calc(int x, int y, int s){
    if(f[x][y][s+100]>-INF) return f[x][y][s+100];
    for(int i=0;i<e[x].size();i++){
        int v=-calc(e[x][i],y,s+d[e[x][i]]);
        if(v>f[x][y][s+100]) f[x][y][s+100]=v;
    }
    for(int i=0;i<e[y].size();i++){
        int v=-calc(x,e[y][i],s-d[e[y][i]]);
        if(v>f[x][y][s+100]) f[x][y][s+100]=v;
    }
    if(f[x][y][s+100]<=-INF) f[x][y][s+100]=-s;
    return f[x][y][s+100];
}
int main(){
    int n,m,x,y;
    while(scanf("%d%d%d%d",&n,&m,&x,&y)>0){
        memset(f,192,sizeof(f));
        for(int i=0;i<n;i++){
            scanf("%d",&d[i]);
            e[i]=vector<int>();
        }
        for(int i=0;i<m;i++){
            int p,q;
            scanf("%d%d",&p,&q);
            e[p].push_back(q);
        }
        printf("%d ",calc(x,y,1));
        int sum=0;
        for(int i=0;i<e[x].size();i++){
            int v=-calc(e[x][i],y,1+d[e[x][i]]);
            if(v==f[x][y][101]) sum++;
        }
        for(int i=0;i<e[y].size();i++){
            int v=-calc(x,e[y][i],1-d[e[y][i]]);
            if(v==f[x][y][101]) sum++;
        }
        if(!sum) sum=1;
        printf("%d\n",sum);
    }
}