意甲冠军：
为了范围[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 __int64
int 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;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。