Gym - 101170A[DP+思维]

题目链接:https://vjudge.net/problem/Gym-101170A

解题思路:

首先要确定的是，改变次数最多不会超过2*n次，因为n最多40，所以我们只要改变每个数的前两个最高位，肯定可以让n个数有序。

然后我们就可以想办法搞个DP[i][j]表示将前i个数变成有序花了j次的最小值。

为什么是最小值呢，维护最小值就是使得高位尽量小，那么就使得后面的数，更有机会直接改变一次高位就可以取得比之前的数大，也就可以保证改变次数越小。

接下来来考虑一下怎么转移，怎么使得花d次变化使得b大于等于a并且尽量靠近a呢？很明显从高位开始看，b[i]要么变为a[i]，要么变为a[i]+1，如果变成a[i]+1，也就说明后面怎么变都不能大于a，所以在i位置要变为a[i]+1，这就与a的串i位置后面连续的9的个数和这个连续区间b的9的个数有关。这里就不细说，看代码就知道了，在变为a[i]+1之后，把剩余的d让前d个高位不是0的变为0就可以取得最小值了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx = 410;
string ans[45][100];
string a,b,c;
int n,m,cmp[mx],up[45][100];
int suf[mx],cnt[mx],vis[mx];
void output(int x,int d)
{
	if(x==1){
		cout << ans[x][d] << endl;
		return ;
	}
	output(x-1,up[x][d]);
	cout << ans[x][d] << endl;
}
bool full(int p,int d){
	for(int i=p;i<m&&d;i++)
	if(a[i]!='0'){
		a[i] = '0';
		d--;
	}
	return !d;
}
bool check(int d){
	for(int i=m-1;i>=0;i--){
		if(a[i]>c[i]) vis[i] = 1;
		else if(a[i]<c[i]) vis[i] = -1;
		else vis[i] = vis[i+1];
	}
	for(int i=0;i<m&&d;i++){
		int pos = i + suf[i+1];
		int w = suf[i+1] - (cnt[i+1]-cnt[pos+1]);
		if(a[i]!=c[i]){
			if(d-1<w||(d-1==w&&vis[pos+1]==-1)){
				if(c[i]=='9') return 0;
				if(a[i]!=c[i]+1) d--;
				a[i] = c[i] + 1;
				return full(i+1,d); 
			}
			a[i] = c[i],d--;
		}else{
			if(d<w||(d==w&&vis[pos+1]==-1)){
				if(c[i]=='9') return 0;
				a[i] = c[i] + 1,d--;
				return full(i+1,d); 
			}	
		}
	}
	return !d && a >= c;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	ans[0][0] = string(m,'0');
	for(int i=1;i<=n;i++){
		cin >> b;
		for(int j=m-1;j>=0;j--){
			cnt[j] = cnt[j+1];
			if(b[j]=='9') cnt[j]++;
		}
		for(int k=0;k<=2*n;k++){
			ans[i][k] = string(m+1,'9');
			for(int j=0;j<=k;j++){
				c = ans[i-1][k-j];
				if(c.length()!=m) continue;
				for(int w=m-1;w>=0;w--){
					suf[w] = 0;
					if(c[w]=='9') suf[w] = suf[w+1] + 1;
				}
				a = b;
				bool ok = check(j);
				if(ok&&ans[i][k]>a){
					ans[i][k] = a;
					up[i][k] = k-j;
				}
			}
		}
	}
	for(int i=0;i<=2*n;i++)
	if(ans[n][i].length()==m){
		output(n,i);
		break;
	}
    return 0;
}