老题解批量补档。
http://222.180.160.110:61235/contest/3887/problem/2
求出最小的、不含前导零的 \(n\) 位数 \(x\)，满足 \(n-1\) 条限制，第 \(i\) 条限制规定 \(x\) 的第 \(i\) 位和 \(i + 1\) 位的关系（小于、大于、等于、不等于）。
如果正着 DP，也就是说先确定前面的数位再向后 DP，后面的数位就没办法决定选择哪个已有状态进行转移，因为我们没有办法仅凭上一位就得到哪个状态拥有最小的字典序。
但是题解很风轻云淡地给出了一个我一辈子想不出来的 fix：倒着 DP。我们只要保证每次选取最小的可行的下一位即可，这恰好符合字典序的定义。
记录前驱（or 后继？）后输出即可。
namespace XSC062 {
using namespace fastIO;
const int maxm = 15;
const int maxn = 2e3 + 5;
int n;
char s[maxn];
int f[maxn][maxm];
void output(int i, int j) {
print(j);
if (i != n)
output(i + 1, f[i][j]);
return;
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1) + 1;
memset(f, -1, sizeof (f));
for (int i = 0; i <= 9; ++i)
f[n][i] = 0x3f3f3f3f;
for (int i = n - 1; i; --i) {
for (int j = 0; j <= 9; ++j) {
if (s[i] == '>') {
for (int k = j - 1; k >= 0; --k) {
if (~f[i + 1][k])
f[i][j] = k;
}
}
else if (s[i] == '<') {
for (int k = 9; k > j; --k) {
if (~f[i + 1][k])
f[i][j] = k;
}
}
else if (s[i] == '=') {
if (~f[i + 1][j])
f[i][j] = j;
}
else {
for (int k = 9; ~k; --k) {
if (k == j)
continue;
if (~f[i + 1][k])
f[i][j] = k;
}
}
}
}
for (int i = 1; i <= 9; ++i)
if (~f[1][i]) {
output(1, i);
break;
}
return 0;
}
} // namespace XSC062