感觉这道题数据有误啊

回复帖子

@Reaepita 2018-05-23 21:43 回复

RT,其他讨论都列出了这道题的错误

我觉得这道题的某些测试点有问题

标程明显是错的,但是却能将10个测试点AC。

但是题解中的任何标程都不能AC最后一个点

所以那些测试点有误

我的程序 我觉得我的做法是对的,但是有些测试点,我比标准输出少

并且标程连这组数据都跑不过

5 5 4 5 7 5

应输出4

一般的标程都输出7

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=500+10;
int dp[maxn][maxn],col[maxn],cnt[maxn],n,m;
int val[maxn];
int main()
{
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&val[i]);
        if(val[i]!=val[i-1])cnt[++n]=0,col[n]=val[i];
        cnt[n]++;
    }
    for(int i=1;i<=n;i++)
    if(cnt[i]==1)dp[i][i]=2;
    else dp[i][i]=1;
    for(int k=2;k<=n;k++)
    for(int i=1,j=k;j<=n;i++,j++)
    {   
        dp[i][j]=3*n;
        if(col[i]==col[j])
        {
            if(cnt[i]+cnt[j]==2)
            {
                dp[i][j]=dp[i+1][j-1]+1;
                for(int l=i+2;l<j-1;l++)
                if(col[l]==col[i]&&cnt[l]==1)dp[i][j]=min(dp[i][j],dp[i+1][l-1]+dp[l+1][j-1]); 
            } 
            else dp[i][j]=dp[i+1][j-1];
        }
        for(int l=i;l<j;l++)dp[i][j]=min(dp[i][j],dp[i][l]+dp[l+1][j]);
    }
    printf("%d\n",dp[1][n]);
    return 0;
}
@Reaepita 2018-05-23 21:45 回复 举报

我的程序纯属瞎写,但是数据是真的有误,不信看其他讨论

@creed_  2018-08-27 19:26 回复 举报

不对吧,你这个东西想要四步就消掉的条件是可以同时射两颗珠子,而题目的意思应该是不可以的

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。