Posted on 2012-03-22 10:30
C小加 阅读(552)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
细节没有处理好，导致超时了好多次。
对于i和j中间的k，如果i和j能遇见k，i能打败k或者j能打败k，则i就能遇见j，用f[i][j]表示i和j是否能遇见。如果i最终能遇见自己，那么i就有取得胜利的可能。
没有开大数组的必要，直接取余就可以。得看明白那些是最优子结构，否则你没办法DP。
时间复杂度为O(n^3)
//NYOj110
//Time:732 Memory:720
#include<iostream>
#include<cstdio>
#include<cstring>
//#include<>
using namespace std;
bool a[503][503];
bool f[503][503];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
memset(f,0,sizeof(f));
for(int i=0;i<n;i++)
{
f[i][(i+1)%n]=1;
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<n;j++)
{
int e=(j+i)%n;
if(f[j][e]) continue;
for(int k=(j+1)%n;k!=e;k++,k%=n)
{
if(f[j][k]&&f[k][e]&&(a[j][k]||a[e][k]))
{
f[j][e]=1;
break;
}
}
}
}
int ans=0;
for(int i=0;i<n;i++)
{
if(f[i][i]) ans++;
}
printf("%d\n",ans);
}
return 0;
}