程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3565 Bi-peak Number 數位dp

hdu 3565 Bi-peak Number 數位dp

編輯：C++入門知識

hdu 3565 Bi-peak Number 數位dp

題意：各位數字先增後減的數稱為峰值數（位數大於等3且第一位非零），然後兩個峰值數連在一起是一個Bi-peak數，

求兩個數之間Bi-peak數的各位數字之和的最大值。

思路：設dp[pos][i][j]表示當前考慮pos位，之前的數位為i，狀態為j,與之後(pos+1)位組合構成Bi-peak number,這(pos+1)位數位和的

最大值。狀態總共有7種,st=0,初始狀態；st=1，恰好有一個在第一個波峰的上坡上；st=2,前面至少有兩個在第一個波峰的上

坡上; st=3,在第一個波峰的下坡上; st=4,前面恰好有一個在第二個波峰的上坡上; st=5,前面至少有兩個在第二個波峰的上坡上; st=6,在

第二個波峰的下坡上。詳見代碼：

/*********************************************************
  file name: hdu3565.cpp
  author : kereo
  create time:  2015年02月09日 星期一 17時29分50秒
*********************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef unsigned long long ll;
const int sigma_size=26;
const int N=10;
const int MAXN=100;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=1000000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair
#define mk(x,y) make_pair((x),(y))
ll A,B;
int bit1[MAXN],bit2[MAXN];
int dp[MAXN][N][N]; //dp[pos][i][j]表示當前考慮pos位，之前的數位為i，狀態為j,與之後(pos+1)位組合構成Bi-peak number,這(pos+1)位數位和的最大值
int dfs(int pos,int pre,int st,int flag1,int flag2){
    if(pos == -1) return st == 6 ? 0 : -inf;
    if(flag1 && flag2 && dp[pos][pre][st]!=-1)
        return dp[pos][pre][st];
    int Min=flag1 ? 0 : bit1[pos];
    int Max=flag2 ? 9 : bit2[pos];
    int ans=-inf;
    for(int i=Min;i<=Max;i++){
        int tmp=0;//一定要初始化
        if(st == 0 && i)
            tmp=1;
        else if(st == 1){
            if(i>pre)
                tmp=2;
            else
                tmp=-1;
        }
        else if(st == 2){
            if(i == pre)
                tmp=-1;
            else if(i>pre)
                tmp=2;
            else 
                tmp=3;
        }
        else if(st == 3){
            if(ipre)
                tmp=4;
            else{
                if(i)
                    tmp=4;
                else 
                    tmp=-1;
            }
        }
        else if(st == 4){
            if(i>pre)
                tmp=5;
            else 
                tmp=-1;
        }
        else if(st == 5){
            if(i>pre)
                tmp=5;
            else if(iMin,flag2 || i