Posted on 2012-03-22 10:30
C小加 閱讀(565)
評論(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;
}