题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3565
题意：给你一个区间，让你找这个区间内有两个山峰的数的最大和，什么是两个山峰，比如121121 第一个2 和第二个2就是两个峰
题解：求的这个不满足dfs(y)-dfs(x)所以只有用一个上限和一个下限来限制
s=0：前导0的状态；
s=1：第一个山峰的上坡，且不能立马下坡；
s=2：第一个山峰的上坡，且最后一点能看成是最高点，下一个点可以是下坡；
s=3：第一个山峰的下坡；
s=4：第二个山峰的上坡，且不能立马下坡；
s=5：第二个山峰的上坡，且最后一点能看成是最高点，下一个点可以是下坡；
s=6：第二个山峰的下坡；
s=-1：其余不合法的状态。
设dp[i][j][k]为考虑第i位，上一个数字为j,状态s为k的最大数位和
1 #include<cstdio> 2 #define MAX(a,b) ((a)>(b)?(a):(b)) 3 #define F(i,a,b) for(int i=a;i<=b;i++) 4 5 int dp[25][10][7],ss[25],ee[25],t,len,an;unsigned __int64 x,y; 6 7 int dfs(int pos,int pre,int s,int fx,int fy){ 8 if(!pos)return s==6?0:-1; 9 if(!fx&&!fy&&dp[pos][pre][s]!=-2)return dp[pos][pre][s]; 10 int st=fx?ss[pos]:0,end=fy?ee[pos]:9,ans=-1,tp,ns; 11 F(i,st,end){ 12 ns=s; 13 if(!s&&i)ns=1; 14 else if(s==1){if(i>pre)ns=2;else ns=-1;} 15 else if(s==2){if(i<pre)ns=3;else if(i==pre)ns=-1;} 16 else if(s==3&&i>=pre){if(i)ns=4;else ns=-1;} 17 else if(s==4){if(i>pre)ns=5;else ns=-1;} 18 else if(s==5){if(i<pre)ns=6;else if(i==pre)ns=-1;} 19 else if(s==6&&i>=pre)ns=-1; 20 if(ns!=-1)tp=dfs(pos-1,i,ns,fx&&i==st,fy&&i==end),ans=(tp==-1?ans:MAX(ans,i+tp)); 21 } 22 if(!fx&&!fy)dp[pos][pre][s]=ans; 23 return ans; 24 } 25 26 int main(){ 27 F(i,0,24)F(j,0,9)F(k,0,6)dp[i][j][k]=-2; 28 scanf("%d",&t); 29 F(i,1,t){ 30 scanf("%I64u%I64u",&x,&y); 31 for(len=0;y;x/=10,y/=10)ss[++len]=x%10,ee[len]=y%10; 32 an=dfs(len,0,0,1,1),printf("Case %d: %d ",i,an==-1?0:an); 33 } 34 return 0; 35 }