BZOJ 4029 [HEOI2015] 定价 ( 数位DP/贪心 )

前言

最近学了数位DP，感觉挺简单又实用。这道题就比较水，可以用300B的贪心过掉…网上似乎大多是贪心的题解，我就写写DP的做法

---

题意

• 给出正整数区间$[L,R]$，定义荒谬值为 (去掉后导零的数的长度)*2-[去掉后导零之后末位为5]。求荒谬值最小的数。若有多个则输出最小值。
• 状态定义为 $(i,s,cnt0,flg,f_l,f_r)$
  • $int i$：表示当前在第 $i$ 位(最低位为 $1$ )
  • $int j$：有效长度为 $s$，即从第一个非零位开始记的长度
  • $int cnt0$：末尾有几个零
  • $bool flg$：去掉后导零之后末位是否为 $5$
  • $bool f_r$：是否达到下限
  • $bool f_r$：是否达到上限
• 这里的 $f_l,f_r$ 是数位DP常用的限制数字大小的方法
• 因为既要保证荒谬值，又要答案最小，就用一个结构体存下荒谬值和对应的最小答案就行了。转移十分简单。因为数的长度最大为 $10$，状态数为$O(10*10*10*2*2*2)=O(8000)$
• 要注意每次都要清零，因为即使 状态一样且没有达到上限或者下限 的时候最小答案也会受$[L,R]$的影响 (没看懂的先看代码，再看下面的$Upd$)
• 还有注意存$L$、$R$的数组也要清零

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
", solve(L, R));
	}
}

$Upd:$之所以会受影响，是因为我算答案的时候，带入了$tmp$计算。第一次进去的时候能保证数答案在$[L,R]$内，但如果记忆化后$[L,R]$改变了，就不能保证在区间里面。