Arranging Hat

题目大意：

给你n,m n个m位的数，保证m位，问要是n个按照从小到大排序，求改变最少个数字，使得这n个按照不递增排序，求最后排序的结果。

//dp[i][j] 表示前i个数，修改不超过j次的最小值。 dp[i][j]向dp[i+1][j+k]转移
//pre[i][j]表示第i个数修改j次是由第i-1个数修改pre[i][j]次转移过来的。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
//dp[i][j] 表示前i个数，修改不超过j次的最小值。 dp[i][j]向dp[i+1][j+k]转移
//pre[i][j]表示第i个数修改j次是由第i-1个数修改pre[i][j]次转移过来的。
string dp[45][500],unite,str[45];
int pre[45][500];
char a[45][500];
int n,m;

string judge(int x){
    string ans;
    ans.clear();
    for(int i=0;i<m;i++){
        int num=a[1][i]-'0';
        if(num&&x) {
            x--;
            ans+='0';
        }
        else ans+=num+'0';
    }
    return ans;
}
bool Min(string u,string v){
    for(int i=0;i<m;i++){
        if(u[i]!=v[i]){
            if(u[i]>v[i]) return false;
            return true;
        }
    }
    return true;
}

string judge(string ss,int x,int k){
    // printf("k=%d\n",k);
    string ans;ans.clear();
    int cnt=0,mark=-1,sum=k;
    for(int i=0;i<m;i++){
        ans+=a[x][i];
        if(a[x][i]!=ss[i]) cnt++;
    }
    if(k==0){
        if(Min(ss,ans)==0) return unite;
        return ans;
    } 

    if(cnt<=k) return ss;
    for(int i=0;i<m;i++){
        if(a[x][i]!=ss[i]){
            if(k) {
                k--;
                ans[i]=ss[i];
                if(k==0) mark=i;
            }
        }
    }
    // printf("mark=%d\n",mark);
    if(Min(ss,ans)) return ans;
    for(int i=mark;i>=0;i--){
        if(ans[i]!='9'){
            ans[i]++;
            int flag=0,num=0;
            for(int j=i+1;j<m;j++) ans[j]=a[x][j];
            for(int j=0;j<m;j++){
                if(ans[j]!=a[x][j]) num++;
            }
            num=sum-num;
            for(int j=i+1;j<m&&num;j++){
                if(ans[j]-'0'){
                    ans[j]='0';
                    num--;
                }
            }
            return ans;
        }
    }
    return unite;
}
//43435
//42431

void init(){
    unite.clear();
    for(int i=1;i<=m;i++) unite+='a';
}


int main(){
    scanf("%d%d",&n,&m);init();
    for(int i=1;i<=n;i++){
        scanf("%s",a[i]);
    }
    int len=100;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=len;j++){
            dp[i][j]=unite;
        }
    }
//    printf("len=%d\n",len);
    for(int i=0;i<=len;i++) dp[1][i]=judge(i);
    for(int i=1;i<n;i++){
        for(int j=0;j<=len;j++){
            for(int k=0;k+j<=len;k++){
                string tmp=judge(dp[i][j],i+1,k);
                // printf("i=%d j=%d k=%d\n",i,j,k);
                // cout<<dp[i][j]<<endl;
                // cout<<tmp<<endl;
                if(Min(dp[i+1][j+k],tmp)==0){
                    // printf("i=%d j=%d k=%d\n",i,j,k);
                    // cout<<dp[i][j]<<endl;
                    // cout<<dp[i+1][j+k]<<endl;
                    // cout<<tmp<<endl;
                    dp[i+1][j+k]=tmp;
                    pre[i+1][j+k]=j;
                    // printf("pre[%d][%d]=%d\n",i+1,j+k,j);
                }
            }
        }
    }
    //printf("www\n");
    int mark=0;
    for(int i=0;i<=len;i++){
//        printf("i=%d ",i);
    //    cout<<dp[n][i]<<endl;
        if(Min(unite,dp[n][i])==0){
            mark=i;
            break;
        }
    }
    // printf("%d\n",mark);
    for(int i=n;i>=1;i--){
        str[i]=dp[i][mark];
        mark=pre[i][mark];
    }
    for(int i=1;i<=n;i++) cout<<str[i]<<endl;
    return 0;
}

/*
5 4 
9999
0000
9999
0000
9999
*/

View Code