Bi-peak Number

  
  

   
   3
12121 12121
120010 120010
121121 121121
  
  

  
  

   
   Case 1: 0
Case 2: 0
Case 3: 8
  
  

其实这一题的难点不在状态，在于它不是找个数，而是去找其中最大的那个（也就是不满足减法原理）

首先说说状态（我设计了6种）

• 当前状态为0，只能转移到1
  
• 当前状态为1，只能转移到2
  
• 当前状态为2，可以转移到2或3
• 当前状态为3，转移到3或4均可
• 当前状态为4，只能转移到5
• 当前状态为5，可以转移到5或6
• 当前状态为6，只能转移到6

转移的时候要注意排除一些不合法的状态

这样，到递归边界的时候只需要判断状态是否为6即可

本来写的记忆化，不过后来发现要求（与求个数不同）。。。。

所以就把记忆化取了，就 T 了。。。。。

至今没想出什么记忆化的方法。。。。。

望高手帮忙

C++ TLE Code

/*http://blog.csdn.net/jiangzh7
By Jiangzh*/
#include<cstdio>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b))
typedef unsigned long long LL;

LL a,b;
int L[30],R[30],len;
int f[30][5][5][15][10];

int predoing(LL a,int *num)
{
	int le=0;
	while(a)
	{
		num[++le]=a%10;
		a/=10;
	}
	return le;
}

int calc(int pos,int d,int u,int last,int sta,int ans)
{
	if(pos==0) return (sta==6)*ans;
	int &res=f[pos][d][u][last][sta];
	//if(res!=-1) return res;
	res=0;
	int st=d?L[pos]:0;
	int ed=u?R[pos]:9;
	for(int i=st;i<=ed;i++)
	{
		if(i==last&&sta!=3) continue;
		int flag=sta;
		if(sta==0)
		{
			if(i!=0) flag=1;
		}
		else if(sta==1)
		{
			if(i>last) flag=2;
			else if(i<last) continue;
			if(i==0) continue;
		}
		else if(sta==2)
		{
			if(i>last) flag=2;
			else if(i<last) flag=3;
		}
		else if(sta==3)
		{
			if(i==0) continue;
			int t=calc(pos-1,d&&i==L[pos],u&&i==R[pos],i,3,ans+i);
			res=max(res,t);
			t=calc(pos-1,4,t);
			continue;
		}
		else if(sta==4)
		{
			if(i>last) flag=5;
			else if(i<last) continue;
		}
		else if(sta==5)
		{
			if(i>last) flag=5;
			else if(i<last) flag=6;
		}
		else{
			if(i<last) flag=6;
			else continue;
		}
		int t=calc(pos-1,flag,ans+i);
		res=max(res,t);
	}
	return res;
}

int main()
{
	freopen("bipeak.in","r",stdin);
	freopen("bipeak.out","w",stdout);
	while(scanf("%llu%llu",&a,&b)==2)
	{
		memset(f,-1,sizeof(f));
		memset(L,sizeof(L));
		memset(R,sizeof(R));
		len=predoing(a,L);
		len=max(len,predoing(b,R));
		printf("%dn",calc(len,1,0));
	}
	return 0;
}