Educational Codeforces Round 76 (Rated for Div. 2)E(dp||贪心）

题：https://codeforces.com/contest/1257/problem/E

题意：给定3个数组，可行操作：每个数都可以跳到另外俩个数组中去，实行多步操作后使三个数组拼接起来形成升序。

　　　输出最小操作次数

dp：

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5;
int dp[M][3];
int a[M];
///dp[i][0]表示前i个数全属于第一个数组所要花费的最小代价
///dp[i][1]表示前i个数全属于第一、二个数组所要花费的最小代价
///！！dp[i][1]必须要保证前i个数是要连续的属于第一个数组，和连续的属于第一个数组前后分布
int main(){
    int k1,k2,k3;
    scanf("%d%d%d",&k1,&k2,&k3);
    int n=k1+k2+k3;
    for(int i=1,x;i<=k1;i++){
        cin>>x;
        a[x]=0;
    }
    for(int i=1,x;i<=k2;i++){
        cin>>x;
        a[x]=1;
    }
    for(int i=1,x;i<=k3;i++){
        cin>>x;
        a[x]=2;
    }
    for(int i=1;i<=n;i++){
        dp[i][0]=dp[i-1][0]+(a[i]==0?0:1);
        dp[i][1]=min(dp[i-1][0],dp[i-1][1])+(a[i]==1?0:1);
        dp[i][2]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+(a[i]==2?0:1);
    }
    cout<<min(dp[n][0],min(dp[n][1],dp[n][2]));
    return  0;
}

View Code

贪心：

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5;
int a[M],b[M];
int main(){
    int n;
    int k1,k2,k3;
    scanf("%d%d%d",&k1,&k2,&k3);
    n=k1+k2+k3;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+k1);
    sort(a+k1,a+k1+k2);
    sort(a+k1+k2,a+n);
    int tot=0;
    for(int i=0;i<n;i++){
        if(b[tot]<a[i])
            b[++tot]=a[i];
        else{
            int pos=upper_bound(b,b+tot,a[i])-b;
            b[pos]=a[i];
        }

    }
    printf("%d\n",n-tot);return 0;
}

View Code