回文&升降数位dp

题目链接：here

Problem G: 等凹数字

Description

定义一种数字称为等凹数字，即从高位到地位，每一位的数字先非递增再非递减，不能全部数字一样，且该数是一个回文数，即从左读到右与从右读到左是一样的，仅形成一个等凹峰，如543212345，5544334455是合法的等凹数字，543212346，123321，111111不是等凹数字。现在问你[L,R]中有多少等凹数字呢？

Input

第一行一个整数T，表示数据的组数。

接下来T行每行俩个数字L和R，(1<=L<=R<=1e18)

Output

输出一个整数，代表[L,R]中有多少等凹数字

Sample Input

2 1 100 101 200

Sample Output

0 1

HINT

小于等于2位的数字无凹峰

补半年前的题~

标称：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 long long dp[20][20][10][2][2][2];
 4 int num[20];
 5 int s[20];
 6 //            当前位   前一位  升过？  降过？上一位最大？ 前导零  长度      回文？
 7 long long rec(int i,int pre,int up,int down,  int flag,   int q, int len, int ispa)
 8 {
 9     if(i<0) return up&&down&&ispa;
10     if(~dp[i][len][pre][up][down][ispa]&&!flag&&!q)return dp[i][len][pre][up][down][ispa];
11     long long res=0;
12     int o=s[i];
13     for(int j=0;j<10;j++)
14     {
15         num[i]=j;
16         if(j>o&&flag)break;
17         if(q)res+=rec(i-1,j,0,0,j<o?0:flag,q&&j==0,len-(q&&j==0),ispa);
18         else if(j==pre)
19         {
20             if(ispa&&i<len/2)
21             res+=rec(i-1,j,up,down,j<o?0:flag,q&&j==0,len,j==num[len-i-1]);
22             else res+=rec(i-1,j,up,down,j<o?0:flag,q&&j==0,len,ispa);
23         }
24         else if(j>pre)
25         {
26             if(!down)continue;
27             if(ispa&&i<len/2)
28             res+=rec(i-1,j,1,down,j<o?0:flag,q&&j==0,len,j==num[len-i-1]);
29             else res+=rec(i-1,j,1,down,j<o?0:flag,q&&j==0,len,ispa);
30         }
31         else if(j<pre)
32         {
33             if(up)continue;
34             if(ispa&&i<len/2)
35             res+=rec(i-1,j,up,1,j<o?0:flag,q&&j==0,len,j==num[len-i-1]);
36             else res+=rec(i-1,j,up,1,j<o?0:flag,q&&j==0,len,ispa);
37         }
38     }
39     if(!flag&&!q)dp[i][len][pre][up][down][ispa]=res;
40     return res;
41 }
42 long long cal(long long x)
43 {
44     int len=0;
45     while(x)
46     {
47         s[len++]=x%10;
48         x/=10;
49     }
50     return rec(len-1,0,0,0,1,1,len,1);
51 }
52 int main()
53 {
54     memset(dp,-1,sizeof(dp));
55     long long l,r;
56     int t;
57     scanf("%d",&t);
58     while(t--){
59     scanf("%lld%lld",&l,&r);
60     printf("%lld
",cal(r)-cal(l-1));
61     }
62     return 0;
63 }

View Code

修改了一下，提交不了，应该是可以过了~

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 ll dp[20][20][10][2][2][2];
 5 int bit[20];
 6 int num[20];
 7 
 8 ll l,r;
 9 
10 ll dfs(int len,int cur,int pre,int up,int down,int sta,int lim){
11     if(cur<0) return up&&down&&sta;
12     if(!lim&&dp[len][cur][pre][up][down][sta]!=-1) return dp[len][cur][pre][up][down][sta];
13     int maxv=lim?bit[cur]:9;
14     ll ans=0;
15     for(int i=0;i<=maxv;i++){
16         num[cur]=i;
17         if(len==cur){
18             if(i==0) ans+=dfs(len-1,cur-1,i,up,down,sta,lim&&i==maxv);
19             else ans+=dfs(len,cur-1,i,up,down,sta,lim&&i==maxv);
20         }
21         else if(i==pre){
22             if(sta&&cur<(len+1)/2) ans+=dfs(len,cur-1,i,up,down,i==num[len-cur],lim&&i==maxv);
23             else ans+=dfs(len,cur-1,i,up,down,sta,lim&&i==maxv);
24         }
25         else if(i<pre){
26             if(up) continue;
27             if(sta&&cur<(len+1)/2) ans+=dfs(len,cur-1,i,up,1,i==num[len-cur],lim&&i==maxv);
28             else ans+=dfs(len,cur-1,i,up,1,sta,lim&&i==maxv);
29         }else if(i>pre){
30             if(!down) continue;
31             if(sta&&cur<(len+1)/2) ans+=dfs(len,cur-1,i,1,down,i==num[len-cur],lim&&i==maxv);
32             else ans+=dfs(len,cur-1,i,1,down,sta,lim&&i==maxv);
33         }
34     }
35     if(!lim) dp[len][cur][pre][up][down][sta]=ans;
36     return ans;
37 }
38 
39 ll solve(ll x){
40     int pos=0;
41     while(x){
42         bit[pos++]=x%10;
43         x/=10;
44     }
45     memset(num,0,sizeof(num));
46     return dfs(pos-1,pos-1,0,0,0,1,1);
47 }
48 
49 int main(){
50     int t;
51     scanf("%d",&t);
52     memset(dp,-1,sizeof(dp));
53     while(t--){
54         scanf("%lld%lld",&l,&r);
55         printf("%lld
",solve(r)-solve(l-1));
56     }
57     return 0;
58 }