山峰数（hill.in/hill.out） 山峰数是指数字排列中不存在山谷(先降后升)的数，例如0,5,13,12321都是山峰数，101，1110000111都不是山峰数。 现给出n个数，请依次判断它们是否为山峰数，如果不是，输出-1。如果是，求出比它小的数中有多少个山峰数。 【输入格式】 第一行一个数n，表示询问数目。 接下来n行，每一行一个数x，表示询问的数。 【输出格式】 输出有n行，x如果不是山峰数，输出-1。x如果是山峰数，则输出有多少个比它小的山峰数。 【输入样例】 5 10 55 101 1000 1234321 【输出样例】 10 55 -1 715 94708 【数据规模】 20% 数据满足x ≤ 106。 100% 数据满足n ≤ 10, x ≤ 1060 【解法】 数位DP 在数位dp的模板基础上，加入参数nu和isdown，nu表示上一个数填的多少，isdown表示当前是在上升期还是在下降期，然后使用模板记忆化搜索即可。
//数位DP #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<queue> #include<algorithm> #include<vector> #include<cstdlib> #include<cmath> #include<ctime> #include<stack> #define INF 2100000000 #define LL long long #define clr(x) memset(x,0,sizeof(x)) #define ms(a,x) memset(x,a,sizeof(x)) #ifdef win32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; int t; LL dp[65][10][2][2]; int len,a[65]; char str[105]; template <class T> inline void read(T &x) { int flag = 1; x = 0; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') flag = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x<<1)+(x<<3)+ch-'0'; ch = getchar(); } x *= flag; } LL dfs(int pos, int pre, int isdown, int lim) { if(pos == len+1) return 1; if(dp[pos][pre][isdown][lim] != -1) return dp[pos][pre][isdown][lim]; LL ans = 0; int nowpla = lim ? a[pos] : 9; for(int i = 0; i <= nowpla; i++) { if(!isdown) { if(i >= pre) ans += dfs(pos+1, i, 0, lim && i == nowpla); else ans += dfs(pos+1, i, 1, lim && i == nowpla); } else if (i <= pre) ans += dfs(pos+1, i, 1, lim && i == nowpla); } return dp[pos][pre][isdown][lim] = ans; } int main() { freopen("hill.in","r",stdin); freopen("hill.out","w",stdout); scanf("%d\n",&t); while(t--) { scanf("%s",str), len = strlen(str); for(int i = 0; i < len; i++) a[i+1] = str[i] - '0'; bool isdown = 0, ishill = 1; for(int i = 2; i <= len; i++) { if(a[i] < a[i-1]) isdown = 1; if(isdown && a[i] > a[i-1]) { printf("-1\n"); ishill = 0; break; } } if(ishill) ms(-1, dp), cout << dfs(1, 0, 0, 1)-1 << endl; } return 0; }