意甲冠军：

为了范围[X,Y]，的最大位数的范围内的需求高峰和值多少。

双峰是为了满足一些规定数量 你可以切两 /\ /\ 形式。

思维：

dp[site][cur][ok]  site地点  面的数是cur 状态为ok

ok分为7种

0：前面全部数都是0

1：第一个峰数且仅仅有一个数

2：第一个峰数在峰顶（可上可下）

3：第一个峰数在峰底（可进入下一个峰或者继续往下）

4：同1 是第二个峰数

5：同2 是第二个峰数

6：同3 可是不可进入下一个峰数了

代码：

#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"using namespace std;#define ll unsigned __int64int dp[30][10][7];int numx[30],numy[30];int dfs(int site,int cur,int ok,int fa,int fb)  //由于是大小 所以要在中间推断{    if(site==0) return ok==6?0:-1;  //状态6代表成立的数    if(!fa&&!fb&&~dp[site][cur][ok]) return dp[site][cur][ok];  //都不是边界    int Min=fa?

numx[site]:0; //上界 int Max=fb?numy[site]:9; //下界 int ans=-1; //初值 for(int i=Min; i<=Max; i++) { int tep=0; if(ok==0&&i) tep=1; //去前导0 else if(ok==1) { if(i>cur) tep=2; //往上走 else tep=-1; //无法走 } else if(ok==2) { if(i>cur) tep=2; //继续上 else if(i==cur) tep=-1; //相等不能走 else tep=3; //往下 } else if(ok==3) { if(i>cur) tep=4; //跳到第二个峰 else if(i==cur) //相等的话0不能跳，由于不能前导0 { if(i) tep=4; else tep=-1; } else tep=3; //继续下 } else if(ok==4) //下同上 { if(i>cur) tep=5; else tep=-1; } else if(ok==5) { if(i>cur) tep=5; else if(i==cur) tep=-1; else tep=6; } else if(ok==6) { if(i>=cur) tep=-1; //最后仅仅能下不能跳了 else tep=6; } if(tep!=-1) { int sum=dfs(site-1,i,tep,fa&&i==Min,fb&&i==Max); //这位放完 后面的最大值 if(sum!=-1) ans=max(ans,sum+i); //加上这位比大小 } } if(!fa&&!fb) dp[site][cur][ok]=ans; //不是边界保存值 return ans; } int main() { int t,cas=1; cin>>t; memset(dp,-1,sizeof(dp)); while(t--) { ll x,y; scanf("%I64u%I64u",&x,&y); //注意2^64次方 要用无符号64位读入 int cnt=0; while(y) { cnt++; numx[cnt]=x%10; x/=10; numy[cnt]=y%10; y/=10; } int ans=dfs(cnt,0,0,1,1); printf("Case %d: %d\n",cas++,ans==-1?0:ans); } return 0; }

版权声明：本文博客原创文章，博客，未经同意，不得转载。