【数位DP】HDU3565-Bi-peak Number
发布时间:2021-01-29 18:15:12 所属栏目:大数据 来源:网络整理
导读:题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=3565 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 -
题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=3565 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. 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]. ? Input The first line of the input is an integer T (T <= 1000),which stands for the number of test cases you need to solve. Each case consists of two integers “A B” (without quotes) (0 <= A <= B < 2^64) in a single line. ? Output For the kth case,output “Case k: v” in a single line where v is the maximum score. If no bi-peak number exists,output 0. ? Sample Input 3 12121 12121 120010 120010 121121 121121? Sample Output Case 1: 0 Case 2: 0 Case 3: 8 题目意思: 给范围[X,Y],求范围内双峰数位数和最大值是多少。 双峰数定义就是满足一个数 可以分割成两个 / / 的形式。共有7种状态 代码: #include<iostream> #include<cstring> #include<cstdio> #define LL unsigned __int64 using namespace std; const int maxn=30; int Case=1; int numa[maxn]; // 记录a的每一位; int numb[maxn]; // 记录b的每一位; int dp[maxn][10][7]; // dp[i][j][k]表示第i位,切上一位是j,在k状态下的最大值; // 当前位置,前一位数,当前所处的状态,是否是最大值; int dfs(int pos,int pre,int stat,bool ismaxa,bool ismaxb) { if(pos==0) return stat==6?0:-1; if(!ismaxa&&!ismaxb&&dp[pos][pre][stat]>=0) return dp[pos][pre][stat]; int Min=ismaxa?numa[pos]:0; int Max=ismaxb?numb[pos]:9; int ans=-1; for(int i=Min;i<=Max;i++){ int tmp=0; // 临时变量标记当前状态; if(stat==0&&i){ // 刚进入的状态; tmp=1; }else if(stat==1){ // 上坡状态; if(i>pre) tmp=2; else tmp=-1; }else if(stat==2){ // 可上可下状态; if(i<pre) tmp=3; else if(i>pre) tmp=2; else tmp=-1; }else if(stat==3){ // 下状态; if(i>pre) tmp=4; else if(i<pre) tmp=3; else if(i==pre){ if(i) tmp=4; else tmp=-1; } }else if(stat==4){ // 第二个峰的上坡状态; if(i>pre) tmp=5; else tmp=-1; }else if(stat==5){ // 第二个峰的可上可下状态; if(i<pre) tmp=6; else if(i>pre) tmp=5; else tmp=-1; }else if(stat==6){ // 第二个峰的下状态(只有两个峰,所以只可以下); if(i<pre) tmp=6; else tmp=-1; } if(tmp!=-1){ int sum=dfs(pos-1,i,tmp,ismaxa&&i==Min,ismaxb&&i==Max); if(sum!=-1) ans=max(ans,sum+i); // 和加上这位数; } } if(!ismaxa&&!ismaxb) dp[pos][pre][stat]=ans; return ans; } int solve(LL a,LL b) { int pos=0; while(b){ numa[++pos]=a%10; a/=10; numb[pos]=b%10; b/=10; } return dfs(pos,true,true); } int main() { int t; LL a,b; scanf("%d",&t); memset(dp,-1,sizeof(dp)); while(t--){ scanf("%I64u%I64u",&a,&b); int tmp=solve(a,b); printf("Case %d: %dn",Case++,tmp==-1?0:tmp); } return 0; } (编辑:湘西站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |