圆桌游戏_圆桌游戏txt

【问题描述】
有一种圆桌游戏是这样进行的：n个人围着圆桌坐成一圈，按顺时针顺序依次标号为1号至n号。对1< i< n的i来说，i号的左边是i+1号，右边是i-1号。1号的右边是n号，n号的左边是1号。每一轮游戏时，主持人指定一个还坐在桌边的人（假设是i号），让他向坐在他左边的人（假设是j号）发起挑战，如果挑战成功，那么j离开圆桌，如果挑战失败，那么i离开圆桌。当圆桌边只剩下一个人时，这个人就是最终的胜利者。
事实上，胜利者的归属是与主持人的选择息息相关的。现在，你来担任圆桌游戏的主持人，并且你已经事先知道了对于任意两个人i号和j号，如果i向j发起挑战，结果是成功还是失败。现在你想知道，如果你可以随意指定每轮发起挑战的人，哪些人可以成为最终的胜利者？

【输入】
第一行包含一个整数n，表示参加游戏的人数；
接下来n行，每行包含n个数，每个数都是0或1中的一个，若第i行第j个数是1，表示i向j发起挑战的结果是成功，否则表示挑战结果是失败。第i行第i列的值一定为0。

【输出】
一行，包含若干个数，表示可能成为最终胜利者的玩家的标号。标号按从小到大的顺序输出，相邻两个数间用1个空格隔开。

【输入输出样例1】
3
0 1 0
0 0 1
0 1 0

1 3

【输入输出样例1说明】
先指定2号向3号发起挑战，3号离开；再指定1号向2号发起挑战，2号离开。此时1号是最终胜利者。
先指定1号向2号发起挑战，2号离开；再指定1号向3号发起挑战，1号离开。此时3号是最终胜利者。
无论如何安排挑战顺序，2号都无法成为最终胜利者。

【数据规模与约定】
对于30%的数据，n≤7
对于100%的数据，n≤100

30分的做法：搜索。

100分的做法：区间dp
将圆桌拆成链：1,2,3…n-1,n,1,2…n
f[i,j]表示第i个人有没有可能与第j个人相邻（i向左，即 j 在 i 的左边）
f[i,i+n]为真 – i有可能成为最终胜利者
枚举i到j之间最后一个出局的人k
i – k – j
k有两种出局方式
① i挑战k成功
② k挑战j失败
如果存在一个k，使得i能与k相邻，k能与j相邻，且k可能以以上两种方式中的一种出局，说明i和j可以相邻
O(n3)

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,f[109][109],dp[209][209],id[209];
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      scanf("%d",&f[i][j]);
    for(int i=1;i<2*n;i++) dp[i][i+1]=1;

    for(int i=1;i<=n;i++) id[i]=i,id[i+n]=i;

    for(int i=2*n-2;i>=1;i--)//倒着枚举，以便向前拓展
    for(int j=i+2;j<=2*n;j++)
    for(int k=i+1;k<j;k++)
    if(dp[i][k]&&dp[k][j]&&(f[id[i]][id[k]]||!f[id[k]][id[j]]))
     dp[i][j]=1;

    for(int i=1;i<=n;i++) if(dp[i][i+n]) printf("%d ",i);
    return 0;
}