The question : We define that each bit is strictly incremented first ( The first is not 0) The number that decreases strictly after is the peak ( such as 1231), A number consisting of two peaks is called bimodal , A bimodal value for each digit and , ask L~R Bimodal maximum value

Ideas : digit DP. Obviously, this problem has something to do with pos of , Related to the former , It's about the current state , We define dp[i][j][k] The first i In front j state k The best situation behind .

The state is 7 Kind of :

0 Nothing ,1 The first ascent in the beginning ,2 It's the first uphill. It can turn ,3 The first downhill 0
4 At the beginning of the second ascent ,5 It's the second uphill that can turn ,6 The second downhill

And then the numbers DP Just a moment .

Be careful , Must open ull,30 Multiple wa Lesson

Code :

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = + ;
const ull seed = ;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + ;
int dp[][][];
//0 Nothing ,1 The first ascent in the beginning ,2 It's the first uphill ,3 The first downhill 0
//4 At the beginning of the second ascent ,5 It's the second uphill ,6 The second downhill
// The first i In front j state k The best situation behind
int top[], low[];
int dfs(int pos, int pre, int st, bool MAXflag, bool MINflag){
if(pos == -)
return st == ? : -INF;
if(!MINflag && !MAXflag && dp[pos][pre][st] != -)
return dp[pos][pre][st];
int Min = MINflag? low[pos] : ;
int Max = MAXflag? top[pos] : ;
int ans = -INF;
for(int i = Min; i <= Max; i++){
int newSt;
if(st == ){
if(i == ) newSt = ;
else newSt = ;
}
else if(st == ){
if(i <= pre) continue;
if(i > pre) newSt = ;
}
else if(st == ){
if(i == pre) continue;
if(i < pre) newSt = ;
else newSt = ;
}
else if(st == ){
if(i < pre) newSt = ;
else if(i > pre) newSt = ;
else{
if(i) newSt = ;
else continue;
}
}
else if(st == ){
if(i <= pre) continue;
newSt = ;
}
else if(st == ){
if(i == pre) continue;
if(i > pre) newSt = ;
else newSt = ;
}
else if(st == ){
if(i >= pre) continue;
newSt = ;
}
ans = max(ans, i + dfs(pos - , i, newSt, MAXflag && i == Max, MINflag && i == Min));
}
if(!MAXflag && !MINflag)
dp[pos][pre][st] = ans;
return ans;
}
int solve(ull l, ull r){
int pos = ;
while(r){
top[pos] = r % ;
low[pos++] = l % ;
r /= ;
l /= ;
}
int ans = dfs(pos - , , , true, true);
return max(, ans);
}
int main(){
int t, ca = ;
memset(dp, -, sizeof(dp));
scanf("%d", &t);
while(t--){
ull l, r;
cin >> l >> r;
printf("Case %d: %d\n", ca++, solve(l, r));
}
return ;
}

HDU 3565 Bi-peak Number( digit DP) More related articles on the solution of the problem

  1. Multi school 5 HDU5787 K-wolf Number digit DP

    // Multi school 5 HDU5787 K-wolf Number digit DP // dp[pos][a][b][c][d][f] The current in pos, The first four numbers are a b c d // f Use as a marker , When the number of enumerations is small now ...

  2. hdu 5898 odd-even number digit DP

    Portal :hdu 5898 odd-even number Ideas : digit DP, It's digital DP The template of a hair can, but pay attention to the lead 0 To deal with ,dp[pos][pre][status][ze] pos: The bits currently processed ...

  3. HDU 5787 K-wolf Number digit DP

    K-wolf Number Problem Description   Alice thinks an integer x is a K-wolf number, if every K adjacen ...

  4. HDU 5179 beautiful number digit dp

    Topic link : hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5179 bc( chinese ): http://bestcoder.hdu.edu.cn/contes ...

  5. HDU 5898 odd-even number ( digit DP) -2016 ICPC Shenyang district network competition

    Topic link The question : A number , The odd numbers in each digit form even length segments , Even bits form odd length segments, which is good . ask [L , R] A good number of . Answer key : Naked digits dp, Consider each digit from high to low , State to save up to the current bit ...

  6. HDU 3709 Balanced Number ( digit DP)

    Balanced Number Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others) ...

  7. hdu 5898 odd-even number( digit dp)

    Problem Description For a number,if the length of continuous odd digits is even and the length of co ...

  8. Answer key ——HDU 4734 F(x) ( digit DP)

    It's still about numbers DP The board question of digit DP There is a striking feature , It's just that the probability of what you're looking for doesn't have much to do with the input , In theory, it is generally the law of number formation Then this problem is to calculate a \( F(A) \) The formula value of , Then seek \( \left [ 0 ...

  9. Answer key ——HDU 2089 Don't 62( digit DP)

    I'm learning digital recently DP It should be an introductory question set up \( dp[i][0/1] \) To \( i \) When a , Whether the former is 6 The number of the numbers that satisfy the conditions And then there's the routine Be careful \( limit \) The restrictions on the transfer of information and ...

  10. HDU 2089 Don't 62 ( digit DP) Answer key

    Ideas : Detailed explanation digit DP Introductory questions dp[pos][sta],pos Which number is the current number of digits ,sta Represents the current state , Because as long as it doesn't appear in the title 64, So there are only two kinds of current states : The first one is 6 Or not . #include<io ...

Random recommendation

  1. SQL Server Tuning Series 2 ( How to use aggregate syndication (Hint) Guide statement running )

    Preface Last time we analyzed the query Hint Usage of , As the first of the last playful modules in the tuning series . If you are interested, you can click to view :SQL Server Play in tuning series ( How to use query tips (Hint) Guide statement running ) This article continues to play the module ...

  2. ASP.Net MVC-Web API Use Entity Framework When I met Loop Reference

    Original address :http://www.it165.net/pro/html/201210/3932.html Recently began to study Web API, Fortunately, the first test project had problems @@- When adding Control Time selection [A ...

  3. 【 Euler circuit + Minimum spanning tree 】SD Driving a car @ Shandong 2018 The provincial team has a round of training day1

    Catalog [ Euler circuit + Minimum spanning tree ]SD Driving a car @ Shandong 2018 The provincial team has a round of training day1 PROBLEM Title Description Input Output The sample input Sample output Tips SOLUTION CODE [ Euler circuit + Minimum spanning tree ]SD Driving a car @ ...

  4. day 49-css Add ( End )[ Floating and positioning ]

    Teacher's notes : Previous review : day49 Chaos is a ladder . 1. Previous review HTML HTTP and HTML Document organization <!Doctype html> HTML head <meta> & ...

  5. [Spark][python] from web log To extract from UserID As key value , To form a new RDD

    in the light of RDD, Use keyBy To build key-line Yes : [training@localhost ~]$ cat webs.log 56.31.230.188 - 90700 "GET ...

  6. Columnar database ~clickhouse Underlying storage principle

    brief introduction : Today I will introduce some basic principles of column database One   Data directory Data Catalog Data storage directory , Data according to part Split into multiple folders , Each folder stores the corresponding data and the corresponding meta information file Metadata Table definition statement , Store all tables ...

  7. SQL Sentence of order by 、group by、having、where

    Baidu knows :1.order by yes Sort by field .. Field can be followed by desc Descending ..asc Ascending .. The default is ascending 2.group by It's a group query 3.having and where All belong to conditional filtering The difference is that in general ha ...

  8. centos Solutions to Chinese garbled code

    In the use of CentOS System time , When installing, you may encounter English CentOS System , In this case, install CentOS The system is installed by default ( That is, English ). After installation , All kinds of Chinese garbled code appeared . that , How can we solve this problem . One .Ce ...

  9. httpwebrequest Asynchronous reference

    http://www.cnblogs.com/SanMaoSpace/archive/2011/07/27/2118133.html http://www.cnblogs.com/qianlifeng ...

  10. Luogu P3373 【 Templates 】 Line segment tree 2 Problem solving report

    P3373 [ Templates ] Line segment tree 2 Title Description As the title , A sequence of numbers is known , You need to do three things : 1. Multiply every number in an interval by \(x\) 2. Add... To every number in an interval \(x\) 3. Find the sum of every number in an interval I / O format ...