CodeForces 490E Restoring Increasing Sequence(贪心)

CodeForces 490E

题目大意：给N个正整数，然而这些正整数中间有些数字是被‘？’遮挡住了，每个‘？’可以还原回一个数字，希望给定的这N个整数形成一个递增的序列。可以的话，给出这N个整数的序列，不行返回N0.

解题思路：每个整数都在满足条件的情况下尽量的小，写了一个非递归版本的，发现要考虑的因素太多了，wa了太多遍。后面改成了递归版本的，但是这个比较耗时。

代码:

#include <cstdio>
#include <cstring>const int MAXL = 10;
const int MAXN = 1e5 + 5;
char str[MAXN][MAXL];
int len[MAXN];int N;bool dfs (int i, int l1, int flag) {            if (l1 >= len[i]) {         if (flag)return true;return false;}if (str[i][l1] != '?') {if (!flag && str[i][l1] < str[i - 1][l1])return false;return dfs(i, l1 + 1, flag | str[i][l1] > str[i - 1][l1]);} else {if (flag) {str[i][l1] = '0';if (dfs(i, l1 + 1, flag))return true;str[i][l1] = '?';return false;}for (char k = str[i - 1][l1]; k <= '9'; k++) {str[i][l1] = k;if (dfs(i, l1 + 1, k > str[i - 1][l1]))return true;    }str[i][l1] = '?';return false;}
}bool judge(int i) {if (len[i] < len[i - 1])return false;if (len[i] > len[i - 1]) {if (str[i][0] == '?')str[i][0] = '1';for (int j = 1; j < len[i]; j++)if (str[i][j] == '?')str[i][j] = '0';return true;}if (dfs(i, 0, 0))return true;return false;
}bool handle () {if (N == 1)return true;for (int i = 1; i < N; i++) if (!judge(i))return false;return true;
}void handle_first() {int len = strlen(str[0]);for (int i = 0; i < len; i++)if (str[0][i] == '?')str[0][i] = (i == 0) ?'1' : '0';
}int main () {while (scanf ("%d", &N) != EOF) {for (int i = 0; i < N; i++) {scanf ("%s", str[i]);len[i] = strlen(str[i]);}handle_first();if (handle()) {printf ("YES\n");for (int i = 0; i < N; i++)  printf ("%s\n", str[i]);} elseprintf ("NO\n");}return 0;
}