E. The Contest Educational Codeforces Round 76 (Rated for Div. 2)

题意： 给出三个序列的值（ 1到 n），移动三个序列中的一些值，使得第一个序列是1 ~ n的一个前缀，第三个序列为1~ 2的一个后缀，第二个序列是其他的值。问移动次数的最小值。

分析：

先放个例子。

• 我们试着写出每个值所属的序列：13123 (这就是1,2,3,4,5每个值所在的组)。

• 问题就转变为给你一段只有1,2,3三个值的序列，通过改变最少次数的值（只能改为1，2，3之一），使序列某前缀全为1，某后缀全为3，其他部分为2。

• 用 $dp[i] [j] $ 表示将第 i 位的值改为 j （即 i 在第 j 组）时的前i位满足题意的改动次数。转移见代码注释。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MA=2e5+5;

int a[5],vis[MA],dp[MA][5];

int main()
{
    int n=0;
    scanf("%d%d%d",&a[0],&a[1],&a[2]);
    for(int k=0;k<=2;++k){
        n=a[k];
        int x;
        for(int i=0;i<n;++i){
            scanf("%d",&x);
            vis[x]=k+1;        //构造新序列
        }
    }
    n=a[0]+a[1]+a[2];
    for(int i=1;i<=n;++i){
        if(vis[i]==1){  
            dp[i][1]=dp[i-1][1]; 
            dp[i][2]=min(dp[i-1][2]+1,dp[i-1][1]+1);   
            dp[i][3]=min(dp[i-1][1]+1,min(dp[i-1][2]+1,dp[i-1][3]+1));
        }
        else if(vis[i]==2){
            dp[i][1]=dp[i-1][1]+1;
            dp[i][2]=min(dp[i-1][1],dp[i-1][2]);
            dp[i][3]=min(dp[i-1][1]+1,min(dp[i-1][2]+1,dp[i-1][3]+1));
        }
        else if(vis[i]==3){
            dp[i][1]=dp[i-1][1]+1;
            dp[i][2]=min(dp[i-1][1]+1,dp[i-1][2]+1);
            dp[i][3]=min(dp[i-1][1],min(dp[i-1][2],dp[i-1][3]));
        }
    }
    printf("%d\n",min(dp[n][1],min(dp[n][2],dp[n][3])));
    return 0;
}

原文：https://www.cnblogs.com/A-sc/p/11873098.html