Palindromic Numbers LightOJ - 1205
2018-06-17 21:49:38来源:未知 阅读 ()
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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Add Two Numbers 2019-08-16
- POJ3252Round Numbers(数位dp) 2018-09-18
- Easy Game LightOJ - 1031 2018-06-27
- N Queen Again LightOJ - 1061 2018-06-27
- POJ 1016 Numbers That Count 不难,但要注意细节 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash