TCO SRM779 DIV1 ArraySorting dp

题意

给一个数组可以把任意个改变成你想要的任意值，问最小改变多少个可以实现非严格递增序列，并且求字典序最小的方案 数据范围都是[1,2000]

思路

一开始写了个笨b贪心WA了，由于数据范围较小，可以考虑n方的算法,dp一下，怎么dp呢，首先改变的值和后续改变息息相关 我们假设一维为改变的值，那么另外一维肯定是位置了，我们可以设dp[i][j]表示对于i的值改成j（如果刚好为a[i]就不用改）[1,i]满足非严格递增条件所需要的最小改变次数。那么就有转移
dp[i][j]=min(dp[i-1][1...j])+int(j!=a[i])
其中min可以用前缀最小值维护一下
求出值后我们得到了相应的dp数组，那么对于求方案而言 应为要求字典序最小所有我们在满足每个dp的位置都尽可能取小的值，由于dp数组的定义是[1...i]满足非严格递增序列 所以我们肯定是从后往前取，才能保证一直满足要求。并且肯定是有解的，因为是dp过来的每种情况都考虑了。所有只要从后往前取该位使得dp[i]最小的j 然后再更新前一位j得可行取值域即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+5;
int dp[maxn][maxn];
struct ArraySorting{
    vector<int> arraySort(vector<int>a){
        int n=a.size();
        int up=*max_element(a.begin(),a.end());
        for(int i=0;i<n;i++){
            int mi=10000;
            for(int j=1;j<=up;j++){
                int z= a[i]==j?0:1;
                if(i==0)dp[i][j]=z;
                else {
                    mi=min(dp[i-1][j],mi);
                    dp[i][j]=mi+z;
                }
            }
        }
        int p=up;
        vector<int>ans;
        for(int i=n-1;i>=0;i--){
            int tmp=10000;
            int id=0;
            for(int j=p;j>=1;j--){
                if(dp[i][j]<=tmp){
                    id=j;
                    tmp=dp[i][j];
                }
            }
            //cout<<dp[i][id]<<" "<<id<<endl;
            ans.push_back(id);
            p=id;
        }
        reverse(ans.begin(),ans.end());
    //  for(auto p:ans)cout<<p<<" ";
        return ans;
    }
};
/*int main(){
ArraySorting t;
int n,x;
cin>>n;vector<int>a;
for(int i=1;i<=n;i++)cin>>x,a.push_back(x);
t.arraySort(a);
    return 0;
}*/

TCO SRM779 DIV1 ArraySorting dp

原文：https://www.cnblogs.com/ttttttttrx/p/12398508.html