Description 定义hill number为各位数字从高位到低位先增再减，也可以只增或只减，现在给出一个整数s，首先判断s是否是一个hill number，如果是则统计所有不大于s的hill number数量 Input 第一行一整数T表示用例组数，每组用例输入一个长度不超过70位的数字串表示s Output 如果s不是一个hill number则输出-1，否则输出1~s中有多少hill number Sample Input 5 10 55 101 1000 1234321 Sample Output 10 55 -1 715 94708 Solution 数位DP，多加一维state表示当前在增还是在减，如果在减则只能继续减，如果在增可以增也可以减 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 77 int T; ll dp[77][11][2]; char s[maxn]; ll dfs(int pos,int pre,int state,int fp) { if(pos<0)return 1; if(!fp&&dp[pos][pre][state]!=-1)return dp[pos][pre][state]; ll ans=0; int fpmax=fp?s[pos]-'0':9; if(state) { for(int i=0;i<=min(fpmax,pre-1);i++) ans+=dfs(pos-1,i,0,fp&&i==fpmax); for(int i=pre;i<=fpmax;i++) ans+=dfs(pos-1,i,1,fp&&i==fpmax); } else { for(int i=0;i<=min(fpmax,pre);i++) ans+=dfs(pos-1,i,0,fp&&i==fpmax); } if(!fp)dp[pos][pre][state]=ans; return ans; } int main() { memset(dp,-1,sizeof(dp)); scanf("%d",&T); while(T--) { scanf("%s",s); int len=strlen(s),flag=0,gg=0; for(int i=0,j=len-1;i<j;i++,j--)swap(s[i],s[j]); for(int i=0;i<len-1;i++) { if(s[i]<s[i+1]&&flag) { gg=1; break; } if(s[i]>s[i+1])flag=1; } if(gg)printf("-1\n"); else { printf("%I64d\n",dfs(len-1,0,1,1)-1); } } return 0; }