10306 Prison break

时间限制:1000MS  内存限制:65535K
提交次数:17 通过次数:4

题型: 编程题   语言: 无限制
Description

Mike was going to escape from the prison when he knew how to do it. However, many other people realized his secret and asked him for help. But,
to avoid being caught by guards, Mike could only take one people with him. By thinking for a minute, an idea came out in his mind to choose one
from all the people who wanted to break the prison:
Let all the n people (assuming they are numbered from 0 to n-1) gather together in a circle and play a game, the one who wins in the end might
have a chance to escape with Mike.
Here is the rule of the game:
Select two people adjacent to each other in the circle randomly, and then they might fight between each other. The loser in the fight has to quit
the game and the winner can stay. Repeat this step until there is only one person left and this person can go with Mike.  
As Mike was a clever man (even though not so careful for letting others know his plan), he knew exactly who will win between i and j before the
two people fight each other, and he draw a n*n matrix G in which G(i,j)=1 means i can win j during the game, while G(i,j)=0 in opposite. And now,
Mike would like to know the list of the people who cannot escape with him no matter in which order the fights are arranged, can you help him?




输入格式

The first line of the input is an integer T indicating the number of the case, and in each case, the first line of the case is an integer n
indicating the number of people. Then a n*n matrix G follows whose meaning has been shown above. (1 <= n <= 100)



输出格式

You should output the numbers of the people who might not have a chance to escape in any situations. These numbers should be printed out in
ascending order and there is only one number in each line. If everyone might have a chance to escape, print out “none” instead.



输入样例

2
4
0 0 0 0
1 0 0 0
1 1 0 0
1 1 1 0
4
0 0 0 1
1 0 1 0
1 0 0 1
0 1 0 0



输出样例

0
1
2
none



提示

4
0 0 0 1
1 0 1 0
1 0 0 1
0 1 0 0
Let us see this sample:
Since 0 can beat 3, 3 beats 1 and 1 beats 2, so 0 can win the game to escape. It is also easy to find that prisoner 1, 2, 3 might have the chance to win the game. So the output is “none”.

懂的说两句也行  不要求代码

把环复制一次，对得到的两倍长度的串进行DP

什么意思

#include<stdio.h>
#include<string.h>
int meet[220][220],fight[120][120];


main(){
    int T,n,i,j,k,flag;
    scanf("%d",&T);
    while(T--){
        memset(meet,0,sizeof(meet));
        scanf("%d",&n);
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        scanf("%d",&fight[i][j]);
        for(i=0;i<n;i++){
            meet[i][i+1]=meet[i+1][i]=meet[i+n][i+n+1]=meet[i+n+1][i+n]=1;
        }
        for(k=2;k<=n;k++){
            for(i=0;i<n;i++)
            for(j=i+1;j<i+k;j++){
                if(!meet[i][i+k]&&meet[i][j]&&meet[j][i+k]&&(fight[i][j%n]||fight[(i+k)%n][j%n])){
                    meet[i][i+k]=meet[i+k][i]=1;
                    if(i+n<220&&i+k+n<220) meet[i+n][i+k+n]=meet[i+k+n][i+n]=1;
                    break;
                }
            }
        }
        for(i=flag=0;i<n;i++){
            if(!meet[i][i+n]) {
                printf("%d\n",i);
                flag=1;
            }
        }
        if(!flag) printf("none\n");
    }
}


代码在这里  求解释

DP的算法编码往往都很简单，难点在问题模型的构造上。

这个问题从动规的角度是这么建模的：

首先是判断相邻情况，如果A可以和B相邻（开始时他们不一定相邻，但经过某一系列战斗后他们会相邻），B可以和C相邻，并且A或C可以打败B，那么A可以和C相邻。

边界条件是，初始时序号相差1（或 n - 1)的人是相邻的。

n个人是围成一圈的，在判断A是否可以胜出这个问题上可以做如下变换，将圈从A处打断排成一列，以A为列头，再在列的末尾添加一个标志人，那么如果A可以与这个标志人相邻他就可以胜出，否则就不能胜出，迈克也就不可能带走它。

这个标志人怎么定？怎么定都行，但下面的处理更方便，假设A可以分身，那么当A可以遇到它自己时说明他灭了夹在他中间的所有人，他可以胜出。

所以才有将n序列复制一遍添加到原序列末尾的做法，这样i与i+n就是第i个人与他的分身，如果他们能相遇就说明他能胜出。

这么说不知道够不够明白。

关于这个问题还可以有别的方法，比如可以以某个人为根结点，以占胜关系建树，如果这棵树可以覆盖所有的人，那么作为根结点的这个人就可以胜出。

当然这只是个分析模型，实际中并不需要你拿结构体建个树出来，算是进行一遍BFT吧。这个模型所用的空间较动规算法要少，只需要n个单位的辅助数组即可，时间复杂度也是O(n^3)。

有兴趣的话可以实现一下，对比看看这两种算法的实际应用效果。

或者把OJ地址给我，有时间我去看看。

谢谢。   OJ是我们学校的，不对外开放。   其他OJ也有类似的题目 剑客对决

BFT是什么

解释下那个状态方程。。。。不能理解

如果A可以和B相邻（开始时他们不一定相邻，但经过某一系列战斗后他们会相邻），B可以和C相邻，并且A或C可以打败B，那么A可以和C相邻

这就是状态方程的解释

BFT是广度优先遍历的意思，与BFS的差别仅在于目的不同