HDu 3565 Bi-peak Number数ビットdp

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=3565
テーマ:
各数字が先に増減した数をピーク数(桁数が等3より大きく、第1位がゼロではない)と呼び、その後、2つのピーク数がつながって1つのbi-peak数であり、2つの数の間のbi-peak数の各数字の和の最大値を求める.
問題解決の考え方:
数ビットdp,dp[i][j][k]は現在の後にiビットがあることを示し,jは前のビットの数字を示し,kはピークとの状態関係を示す.
k=0は前面がゼロであることを示し、k=1は前面にちょうど1つが第1のピークの上り坂にあることを示し、k=2は前面に少なくとも2つが第1のピークの上り坂にあることを示し、k=3は第1のピークの下り坂にあることを示す
                                        k=4は前方に2番目のピークの上り坂があることを示し、k=5は前方に少なくとも2つのピークが2番目のピークの上り坂にあることを示し、k=6は2番目のピークの下り坂にあることを示す.
ピーク数のビット数は少なくとも3であり、第1のビットはゼロではないことに注意してください.
コード:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF (1<<30)
#define PI acos(-1.0)
using namespace std;

#define ll unsigned __int64

int dp[30][15][7];
//  0      0，  1             ，2              ，3       
                      //  4                           5                             6       
int aa[30],bb[30];

int dfs(int cur,int last,int flag,int aflag,int bflag)
{
   if(!cur) //      
      return (flag==6)?0:-1;

   if(!aflag&&!bflag&&dp[cur][last][flag]!=-1)
      return dp[cur][last][flag];

   int Min=aflag?aa[cur]:0; //  
   int Max=bflag?bb[cur]:9; //  

   int res=-1;
   for(int i=Min;i<=Max;i++)
   {
      int status=0;

      if(flag==0&&i)
         status=1;
      else if(flag==1)
      {
         if(i>last)
            status=2;
         else
            status=-1;
      }
      else if(flag==2)
      {
         if(i<last)
            status=3;
         else if(i==last)
            status=-1;
         else
            status=2;
      }
      else if(flag==3)
      {
         if(i>last)
            status=4;
         else if(i==last)
            {
               if(i)
                  status=4;
               else
                  status=-1;
            }
         else
            status=3;
       }
       else if(flag==4)
       {
          if(i>last)
            status=5;
          else
            status=-1;
       }
       else if(flag==5)
       {
          if(i<last)
            status=6;
          else if(i==last)
            status=-1;
          else
            status=5;
       }
       else if(flag==6)
       {
          if(i<last)
            status=6;
          else
            status=-1;
       }
      if(status!=-1)
      {
         int temp=dfs(cur-1,i,status,aflag&&i==Min,bflag&&i==Max);

         if(temp!=-1)
            res=max(res,i+temp);

      }

   }
   if(!aflag&&!bflag)
      dp[cur][last][flag]=res;
   return res;
}

int main()
{
   int t;

   scanf("%d",&t);

   memset(dp,-1,sizeof(dp));
   for(int ca=1;ca<=t;ca++)
   {

      ll a,b;

      scanf("%I64u%I64u",&a,&b);
      int pos=0;

      while(b)
      {
         ++pos;
         aa[pos]=a%10;
         a/=10;
         bb[pos]=b%10;
         b/=10;
      }
      int ans=dfs(pos,0,0,1,1);

      printf("Case %d: ",ca);
      if(ans!=-1)
         printf("%d
",ans);
      else
         printf("0
");
   }

   return 0;
}