前言
最近学了数位DP，感觉挺简单又实用。这道题就比较水，可以用300B的贪心过掉…网上似乎大多是贪心的题解，我就写写DP的做法
题意
- 给出正整数区间[L,R][L,R][L,R]，定义荒谬值为 (去掉后导零的数的长度)*2-[去掉后导零之后末位为5]。求荒谬值最小的数。若有多个则输出最小值。
- 状态定义为 (i,s,cnt0,flg,fl,fr)(i,s,cnt0,flg,f_l,f_r)(i,s,cnt0,flg,fl,fr)
- int iint\ iint i：表示当前在第 iii 位(最低位为 111 )
- int jint\ jint j：有效长度为 sss，即从第一个非零位开始记的长度
- int cnt0int\ cnt0int cnt0：末尾有几个零
- bool flgbool\ flgbool flg：去掉后导零之后末位是否为 555
- bool frbool\ f_rbool fr：是否达到下限
- bool frbool\ f_rbool fr：是否达到上限
- 这里的 fl,frf_l,f_rfl,fr 是数位DP常用的限制数字大小的方法
- 因为既要保证荒谬值，又要答案最小，就用一个结构体存下荒谬值和对应的最小答案就行了。转移十分简单。因为数的长度最大为 101010，状态数为O(10∗10∗10∗2∗2∗2)=O(8000)O(10*10*10*2*2*2)=O(8000)O(10∗10∗10∗2∗2∗2)=O(8000)
- 要注意每次都要清零，因为即使 状态一样且没有达到上限或者下限 的时候最小答案也会受[L,R][L,R][L,R]的影响 (没看懂的先看代码，再看下面的UpdUpdUpd)
- 还有注意存LLL、RRR的数组也要清零
AC代码
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9+1;
struct node {
int x, y;
node(int _x=0, int _y=0):x(_x), y(_y){}
inline node operator +(const node &t)const {
if(x < t.x) return *this;
if(x > t.x) return t;
return node(x, min(y, t.y));
}
};
node f[11][11][11][2];
bool vis[11][11][11][2];
int dl[11], dr[11];
inline node dfs(int len, int s, int cnt0, bool flg, bool fl, bool fr, int tmp) {
if(!len) return node((flg ? 2*(s-cnt0)-1 : 2*(s-cnt0)), tmp);
if(!fl && !fr && vis[len][s][cnt0][flg]) return f[len][s][cnt0][flg];
node res = node(inf, inf);
int mn = fl ? dl[len] : 0, mx = fr ? dr[len] : 9;
for(int i = mn; i <= mx; ++i)
res = res + dfs(len-1, s+(s||i), i?0:cnt0+1, i ? i==5: flg, fl&&i==mn, fr&&i==mx, tmp*10+i);
if(!fl && !fr) {
vis[len][s][cnt0][flg] = 1;
f[len][s][cnt0][flg] = res;
}
return res;
}
inline int solve(int l, int r) {
memset(dl, 0, sizeof dl); //清零2
memset(dr, 0, sizeof dr);
int lenl = 0, lenr = 0;
while(l) dl[++lenl] = l % 10, l /= 10;
while(r) dr[++lenr] = r % 10, r /= 10;
node res = dfs(lenr, 0, 0, 0, 1, 1, 0);
return res.y;
}
int L, R;
int main () {
int T;
scanf("%d", &T);
while(T--) {
memset(vis, 0, sizeof vis); //清零 1 (让我WA到自闭)
scanf("%d%d", &L, &R);
printf("%d\n", solve(L, R));
}
}
Upd:Upd:Upd:之所以会受影响，是因为我算答案的时候，带入了tmptmptmp计算。第一次进去的时候能保证数答案在[L,R][L,R][L,R]内，但如果记忆化后[L,R][L,R][L,R]改变了，就不能保证在区间里面。