Palindromic Numbers LightOJ - 1205

2018-06-17 21:49:38来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Palindromic Numbers LightOJ - 1205

http://blog.csdn.net/harlow_cheng/article/details/77466732

话说原来记忆化搜索还能回溯...很少见啊,这里回溯实际作用是省去了用别的东西来表示之前选的数字的状态。

注意点:

1.必须要对不同的tot(总长度)记忆化到不同的数组中

2.19行

 1 #include<cstdio>
 2 #include<cstring>
 3 typedef long long LL;
 4 LL ans[30][30][2];
 5 LL w[30];
 6 LL T,l,r;
 7 LL temp[30];
 8 LL dp(LL tot,LL pos,bool pre0,bool limit)
 9 {
10     if(pos<1)    return 1;
11     if(!limit&&ans[tot][pos][pre0]!=-1)
12         return ans[tot][pos][pre0];
13     LL i,res=0,end=limit?w[pos]:9;
14     for(i=0;i<=end;i++)
15     {
16         temp[pos]=i;
17         if(i==0&&pre0)
18             res+=dp(tot-1,pos-1,1,0);
19             //res+=dp(tot,pos-1,1,0);这样会错
20         else if(pos>tot/2)//5-->5,4,3 6-->6,5,4 如果在前一半则可以随便填
21             res+=dp(tot,pos-1,0,limit&&i==w[pos]);
22         else if(temp[pos]==temp[tot-pos+1])//如果在后一半就必须和前一半一样
23             res+=dp(tot,pos-1,0,limit&&i==w[pos]);
24     }
25     if(!limit)    ans[tot][pos][pre0]=res;
26     return res;
27 }
28 LL get(LL x)
29 {
30     if(x<0)    return 0;
31     LL len=0;
32     for(;x>0;x/=10)    w[++len]=x%10;
33     return dp(len,len,1,1);
34 }
35 int main()
36 {
37     LL iii,ttt;
38     memset(ans,-1,sizeof(ans));
39     scanf("%lld",&T);
40     for(iii=1;iii<=T;iii++)
41     {
42         scanf("%lld%lld",&l,&r);
43         if(l>r)    ttt=l,l=r,r=ttt;
44         printf("Case %lld: %lld\n",iii,get(r)-get(l-1));
45     }
46     return 0;
47 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Mirror Number SPOJ - MYQ10

下一篇:FZU 1919 -- K-way Merging sort(记忆化搜索)