NYOJ110 剑客决斗 【动态规划DP,弗洛伊德】

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 06 日

http://acm.nyist.net/JudgeOnline/problem.php?pid=110

描述
在路易十三和红衣主教黎塞留当权的时代,发生了一场决斗。n个人站成一个圈,依次抽签。抽中的人和他右边的人决斗,负者出圈。这场决斗的最终结果关键取决于决斗的顺序。现书籍任意两决斗中谁能胜出的信息,但“A赢了B”这种关系没有传递性。例如,A比B强,B比C强,C比A强。如果A和B先决斗,C最终会赢,但如果B和C决斗在先,则最后A会赢。显然,他们三人中的第一场决斗直接影响最终结果。

假设现在n个人围成一个圈,按顺序编上编号1~n。一共进行n-1场决斗。第一场,其中一人(设i号)和他右边的人(即i+1号,若i=n,其右边人则为1号)。负者被淘汰出圈外,由他旁边的人补上他的位置。已知n个人之间的强弱关系(即任意两个人之间输赢关系)。如果存在一种抽签方式使第k个人可能胜出,则我们说第k人有可能胜出,我们的任务是根据n个人的强弱关系,判断可能胜出的人数。

题解:编号为x的人能从所有人中胜出,必要条件是他能与自己“相遇”,即把环看成链,x点拆成两个在这条链的两端,中间的人全部被淘汰出局,x保持不败。这样,在连续几个人的链中,只须考虑头尾两个人能否胜利会师,中间的则不予考虑,从而少了一维状态表示量。设meet[i,j]记录i和j能否相遇,能相遇则为true,否则为false。状态转移方程为

#include<cstdio>  
#include <cstring>  
using namespace std;  
#define MAX 502  
bool meet[MAX][MAX];  
bool fights[MAX][MAX];  
//动态转移方程:meet[i][j]=meet[i][k]&&meet[k][j]&&i能战胜k或者j能战胜k  
//                  其中meet[i][j]表示编号i,j战士可相遇  
int main(){  
    int n,m;  
    scanf("%d",&n);  
    while(n--){  
        scanf("%d",&m);  
        memset(meet,0,sizeof(meet));  
        for(int i=0;i!=m;i++)  
            for(int j=0;j!=m;j++)  
                scanf("%d",&fights[i][j]);  
        int end;  
        for(int i=0;i<m;i++)  
            meet[i][(i+1)%m]=true;  
        for(int i=2;i<=m;i++){  
            for(int start=0;start!=m;start++){  
                end=(i+start)%m;  
                for(int k=(start+1)%m;k!=end;k++,k%=m){  
                    meet[start][end]=meet[start][end] ||  
                                    meet[start][k]&&meet[k][end] &&  
                                    (fights[start][k]||fights[end][k]);  
                }  
            }  
        }  
        int count=0;  
        for(int i=0;i<m;i++)  
            if(meet[i][i]) count++;  
        printf("%d\n",count);  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期日, 2017 年 10 月 22 日