建议加强数据

回复帖子

@Rainbow_sjy❤OI  2020-02-04 19:02 回复

本题 $n\le 50$ ,然而数据中 $n\le 16$ 。

题解也都是错的, $n=50$ 的数据都会 TLE 。

下面是一个 $n=50$ 的数据可以在 2s 内跑过的程序:(加了一个优化)

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
int n,maxdep,a[55],t[55];
bool ok;
inline bool chk(int l,int r){
    return abs(a[l]-a[r])!=1;
}
bool dfs(int dep,int lst,int lstev)
{
    if(dep+lstev>maxdep)return 0;
    if(!lstev)return 1;
    For(i,2,n)
    {
        if(i==lst||!chk(i,i+1))continue;//加了一个优化
        int ch=-chk(i,i+1);
        reverse(a+1,a+i+1);
        ch+=chk(i,i+1);
        if(dfs(dep+1,i,lstev+ch))return 1;
        reverse(a+1,a+i+1);
    }return 0;
}
signed main()
{
//  clock_t fir=clock();
    n=read();
    For(i,1,n)t[i]=a[i]=read();
    sort(t+1,t+n+1);
    For(i,1,n)a[i]=lower_bound(t+1,t+n+1,a[i])-t;
    a[n+1]=n+1;
    int ev=0;
    For(i,1,n)ev+=chk(i+1,i);
    for(maxdep=0;;++maxdep)
        if(dfs(0,0,ev)){
            cout<<maxdep;
    //      puts("");cout<<clock()-fir;
            return 0;
        }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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