C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

NYOJ 110 剑客决斗(简单DP)

Posted on 2012-03-22 10:30 C小加 阅读(544) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

细节没有处理好,导致超时了好多次。

对于ij中间的k,如果ij能遇见ki能打败k或者j能打败k,则i就能遇见j,用f[i][j]表示ij是否能遇见。如果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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理