M_sea

洛谷3847 [TJOI2007]调整队形
Luogu代码区间DP。设$f[i][j]$表示i到j这段区间的最小操作次数。可以发现,操作1和操作2都可以转换成...
扫描右侧二维码阅读全文
27
2018/07

洛谷3847 [TJOI2007]调整队形

Luogu

代码

区间DP。

设$f[i][j]$表示i到j这段区间的最小操作次数。

可以发现,操作1和操作2都可以转换成操作3。
那么只要考虑操作3和操作4即可。

容易得出状态转移方程:

当$a[i]=a[j]$时,$f[i][j]=f[i+1][j-1]$
当$a[i]\neq a[j]$时,$f[i][j]=min(f[i+1][j-1]+1,f[i+1][j]+1,f[i][j-1]+1)$

边界为$f[i][i]=0$,答案为$f[1][n]$。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int a[3010];
int f[3010][3010];

int main() {
    int n=read();
    for (re int i=1;i<=n;i++) a[i]=read();
    for (re int l=2;l<=n;l++)
        for (re int i=1;i+l-1<=n;i++) {
            int j=i+l-1;
            if (a[i]==a[j]) f[i][j]=f[i+1][j-1];
            else f[i][j]=min(min(f[i+1][j],f[i][j-1]),f[i+1][j-1])+1;
        }
    printf("%d\n",f[1][n]);
    return 0;
}
最后修改:2018 年 11 月 30 日 10 : 04 PM

发表评论