HDOJ 3565 Bi-peak Number (数位DP)

时间:2022-12-16 10:46:34
Problem Description:
A peak number is defined as continuous digits {D0, D1 … Dn-1} (D0 > 0 and n >= 3), which exist Dm (0 < m < n - 1) satisfied Di-1 < Di (0 < i <= m) and Di > Di+1 (m <= i < n - 1).
A number is called bi-peak if it is a concatenation of two peak numbers.

HDOJ 3565 Bi-peak Number (数位DP)


The score of a number is the sum of all digits. Love8909 is crazy about bi-peak numbers. Please help him to calculate the MAXIMUM score of the Bi-peak Number in the closed interval [A, B].
 
分析:由于结果不满足区间减法,所以不能像通常那样计算cal(b)-cal(a-1),正确的处理方法是,在dfs时保存2个标记,一个标记前缀是否达上界,另一个标记是否达下界。然后就是状态分析了,分析清楚了也就简单了,以下是我设计的状态:
s=0:前导0的状态;
s=1:第一个山峰的上坡,且不能立马下坡;
s=2:第一个山峰的上坡,且最后一点能看成是最高点,下一个点可以是下坡;
s=3:第一个山峰的下坡;
s=4:第二个山峰的上坡,且不能立马下坡;
s=5:第二个山峰的上坡,且最后一点能看成是最高点,下一个点可以是下坡;
s=6:第二个山峰的下坡;
s=-1:其余不合法的状态。
HDOJ 3565 Bi-peak Number (数位DP)HDOJ 3565 Bi-peak Number (数位DP)View Code
#include <stdio.h>
#include <string.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define N 20
#define INF 0x7f7f7f7f
typedef unsigned __int64 LL;
int sx[N],sy[N];
int dp[N][10][7];
int dfs(int pos,int last,int s,int fx,int fy)
{
    if(pos==-1) return s==6?0:-1;
    if(!fx&&!fy&&dp[pos][last][s]!=INF)    return dp[pos][last][s];
    int min=fx?sx[pos]:0;
    int max=fy?sy[pos]:9;
    int ret=-1;
    for(int i=min;i<=max;i++)
    {
        int ns=s;
        if(s==0 && i)  ns=1;
        else if(s==1)
        {
            if(i>last)  ns=2;
            else    ns=-1;
        }
        else if(s==2)
        {
            if(i<last)  ns=3;
            else if(i==last)    ns=-1;
        }
        else if(s==3 && i>=last)
        {
            if(i)   ns=4;
            else    ns=-1;
        }
        else if(s==4)
        {
            if(i>last)  ns=5;
            else    ns=-1;
        }
        else if(s==5)
        {
            if(i<last)  ns=6;
            else if(i==last)    ns=-1;
        }
        else if(s==6 && i>=last) ns=-1;
        if(ns!=-1)
        {
            int tmp=dfs(pos-1,i,ns,fx&&i==min,fy&&i==max);
            if(tmp!=-1) ret=MAX(ret,i+tmp);
        }
    }
    if(!fx&&!fy)  dp[pos][last][s]=ret;
    return ret;
}
int main()
{
    int t,kase=0;
    memset(dp,0x7f,sizeof(dp));
    scanf("%d",&t);
    while(t--)
    {
        printf("Case %d: ",++kase);
        LL x,y;
        scanf("%I64u%I64u",&x,&y);
        int pos=0;
        for(;y;x/=10,y/=10) sx[pos]=x%10,sy[pos++]=y%10;
        int ans=dfs(pos-1,0,0,1,1);
        if(ans==-1) ans=0;
        printf("%d\n",ans);
    }
    return 0;
}