本文主要是介绍CodeForces 490E Restoring Increasing Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
一个严格递增序列 某些数字的某些位被盖住了 求 恢复后的序列
思路：
贪心 让每个数在大于前一个的基础上尽量的小
先讨论数字长度
len[i]<len[i-1] 一定是NO
len[i]>len[i-1] 除了第一位如果是？就填1以外 其他？全填0
len[i]==len[i-1] dfs搜索num[i]格式下大于num[i-1]的最小的数
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long LL;
#define N 100010int n, ans = 1;
char a[N][10];
int len[N];bool dfs(int i, int j, int big) {if (j == len[i]) {if (big)return true;return false;}if (a[i][j] != '?') {if (!big && a[i][j] < a[i - 1][j])return false;return dfs(i, j + 1, big | (a[i][j] > a[i - 1][j]));} else {if (big) {a[i][j] = '0';if (dfs(i, j + 1, 1))return true;a[i][j] = '?';return false;} else {for (char k = a[i - 1][j]; k <= '9'; k++) {a[i][j] = k;if (dfs(i, j + 1, k > a[i - 1][j]))return true;}a[i][j] = '?';return false;}}
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%s", a[i]);len[i] = strlen(a[i]);}for (int i = 1; i <= n; i++) {if (len[i] < len[i - 1]) {ans = 0;break;} else if (len[i] == len[i - 1]) {if (!dfs(i, 0, 0)) {ans = 0;break;}} else {if (a[i][0] == '?')a[i][0] = '1';for (int j = 1; j < len[i]; j++) {if (a[i][j] == '?')a[i][j] = '0';}}}if (ans) {puts("YES");for (int i = 1; i <= n; i++)puts(a[i]);} elseputs("NO");return 0;
}这篇关于CodeForces 490E Restoring Increasing Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
