题意：我们定义每一位先严格递增（第一位不为0）后严格递减的数为峰（比如1231），一个数由两个峰组成称为双峰，一个双峰的价值为每一位位数和，问L~R双峰最大价值
思路：数位DP。显然这个问题和pos有关，和前一项有关，和当前状态有关，我们定义dp[i][j][k]第i位前面j状态k的后面的最佳情况。
状态有7种：
0什么都没，1刚开始第一个上坡，2已经第一个上坡了可以转折了，3第一个下坡0
4刚开始第二个上坡，5已经第二个上坡可以转折了，6第二个下坡
然后数位DP一下就好了。
注意，要开ull，30多个wa的教训
代码：
#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什么都没，1刚开始第一个上坡，2已经第一个上坡了，3第一个下坡0
//4刚开始第二个上坡，5已经第二个上坡，6第二个下坡
//第i位前面j状态k的后面的最佳情况
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 ;
}