luogu3847 [TJOI2007] 대형 조정(dp 변환 회문의 최소 조작)

조작은 모두 네 가지가 있지만 우리는 간략화의 원칙에 따라 조작 1, 2, 즉 수열에 수를 더하면 같은 효과가 있을 수 있다는 것을 발견할 수 있다. 한 단계 조작 3, 즉 네가 더하고 싶은 수를 삭제해서 대체할 수 있기 때문에 두 가지 조작이 있다.한 수를 바꾸다.2. 숫자 하나를 삭제한다.최소한 몇 단계의 조작을 거쳐 원수열을 회문으로 바꿀 수 있도록 하려면 dp[i][j]가 i...j를 회문으로 바꾸는 데 필요한 최소 보수를 나타낸다. 만약에 a[i]=a[j]가 dp[i]=dp[j]=dp[i+1][j-1]elsedp[i]=dp[i+1][j][j-1][j-1]+1이 한 수를 바꾸면 dp[i][j]=dp[i+1][j][j]+1]를 삭제하고 a[i][j][j]를 [j]dpi][j][j][j1]를 삭제하면 [ja+1]를 삭제할 수 있다.복잡도 O (n2)

#include 
#define N 3010
int a[N],n,dp[N][N];
inline int min(int x,int y){return xint main(){
//  freopen("a.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int len=2;len<=n;++len){
        for(int i=1;i+len-1<=n;++i){
            int j=i+len-1;
            if(a[i]==a[j]) dp[i][j]=dp[i+1][j-1];
            else dp[i][j]=min(dp[i+1][j-1],min(dp[i+1][j],dp[i][j-1]))+1;
        }
    }
    printf("%d
",dp[1][n]);
    return 0;
}