SPOJ MUSKET

黑书P117页。

要是不看解析，确实不要算和定义状态。

把环看成链，是指把这个1234512345，写两边，然后怎么表示一个人是否胜利了呢？其实就是其他人全部死光（好像等于没说）；

考虑最后一次杀人，也就是说只剩下两个人，他们至少要相邻。其实你会想到这样是很难搞的，枚举一个点，后面的点自相残杀+这个点偶尔去杀一下。很麻烦。

于是，我们要转换一下——最后一个胜利了，例如2， 234512 也就是中间的都死光了，也就是2能和2相邻。

于是就转换为两个相邻的问题。区间DP搞一下

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
char str[105];
int a[105][105];
int vis[105<<1][105<<1];
 
 
bool calc(int l,int r) {
    if(l+1==r) return true;
    if(vis[l][r]!=-1) return vis[l][r];
    for(int k = l+1; k < r; k++) {
        if(calc(l,k)&&calc(k,r)&&(a[l%n][k%n]==1||a[k%n][r%n]==0))
            return vis[l][r] = 1;
    }
    return vis[l][r] = 0;
}
 
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int t;
    scanf("%d",&t);
 
    while(t--) {
 
        memset(vis,-1,sizeof(vis));
 
        scanf("%d",&n);
        for(int i = 0; i< n; i++) {
            scanf("%s",str);
            for(int j = 0; j < n; j++) {
                a[i][j] = str[j] - '0';
            }
        }
 
        vector<int> v;
        for(int i = 0; i<n; i++) {
            if(calc(i,i+n))
                v.push_back(i);
        }
 
        printf("%d
",(int)v.size());
        for(int i = 0; i < (int)v.size(); i++)
            printf("%d
",v[i]+1);
 
    }
 
    return 0;
}