题意：判断小于n的数字中，数位从高到低成上升再下降的趋势的数字的个数
分析：简单的数位DP，保存前一位的数字，注意临界点的处理，都是套路。
#include <bits/stdc++.h> typedef long long ll;
const int N = 70 + 5;
char str[N];
ll dp[N][10][2];
int len; ll DFS(int pos, int pre, int up, int limit) {
if (pos == len) {
return 1;
}
ll &now = dp[pos][pre][up];
if (!limit && now != -1) {
return now;
}
ll ret = 0;
int d = limit ? str[pos] - '0' : 9;
for (int i=0; i<=d; ++i) {
if (up) {
if (i >= pre) {
ret += DFS (pos + 1, i, up, limit && i == d);
} else {
ret += DFS (pos + 1, i, 0, limit && i == d);
}
} else if (i <= pre) {
ret += DFS (pos + 1, i, 0, limit && i == d);
}
}
if (!limit) {
now = ret;
}
return ret;
} int main() {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%s", str);
len = strlen (str);
int flag = -1;
for (int i=1; i<len; ++i) {
if (str[i] < str[i-1]) {
flag = 0;
}
if (flag == 0 && str[i] > str[i-1]) {
flag = 1;
break;
}
}
if (flag == 1) {
puts ("-1");
} else {
memset (dp, -1, sizeof (dp));
printf ("%I64d\n", DFS (0, 0, 1, 1) - 1);
}
}
return 0;
}