题解 P3847 【[TJOI2007]调整队形】

· · 题解

排版已订正。

DP题。

感觉蓝题难度还是有点过了吧？

大致思路就是建一个二维数组dp【i】【j】表示从第i个人到第j个人对称的最小次数

这时候就大致可以得出动态转移方程了，如下

1.先设置一个长度l自2至n枚举

2.此时i从1枚举至n-l+1，j此时则为i+l-1。

3.当第i个人颜色等于第j个人时，dp【i】【j】则与dp【i+1】【j-1】相同，赋值；

4.如果不同的话，则为{dp【i+1】【j】，dp【i】【j-1】，dp【i+1】【j-1】}中次数最少的那一个再+1了。

故状态转移方程代码如下：

if(a[i]==a[j]) dp[i][j]=dp[i+1][j-1];//相同情况
        else dp[i][j]=min(dp[i+1][j],min(dp[i][j-1],dp[i+1][j-1]))+1;

最后输出dp【1】【n】则为正解。

发现了吗？实际上代码很精简的。只要你有心，省选难度在你眼里都将是水题！

PS:初始化会WA第七个点！

#include<bits/stdc++.h>
using namespace std;
int n,a[3001],dp[3001][3001];//dp[i][j]表示i到j对称的最小次数 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int l=2;l<=n;l++)
    for(int i=1;i+l<=n+1;i++)//枚举第i个人
    {
        int j=i+l-1;//枚举第j个人
        if(a[i]==a[j]) dp[i][j]=dp[i+1][j-1];
        else dp[i][j]=min(dp[i+1][j],min(dp[i][j-1],dp[i+1][j-1]))+1;
    }
    cout<<dp[1][n];
}

PPS：这是@M_sea dalao給我们讲解的，深入浅出Orz

PPPS：应该没有题解与这个相似吧？因为我们全机房都是听的M_sea dalao讲解的，所以可能机房会有与我相似的题解投上来QAQ