模板总结
寄搜模板
ll dp[N][state]; // 状态根据题目性质改变, 例子记录数位中 非零 数位的个数
// 从高位向低位递归
ll dfs(int pos, int cnt, bool lead, bool limit){ // (当前数位, 根据题目需要记录状态, 是否有前导零, 前面的数位是否填满)
if(pos == -1) return 1; // 递归出口, 可能需要判断是否符合题目条件
if(!limit && !lead && dp[pos][cnt] != -1) return dp[pos][cnt]; // 记忆化, 具体看题目,一般需要 !limit 与 !lead
int up = limit ? a[pos] : 9; // 根据前面是否填满, 设立枚举上界
/*
灵活修改
if(cnt == k) up = 0;
*/
ll res = 0;
for(int i = 0; i <= up; i++){
/*
灵活修改, 进行递归
int t = (i != 0);
res += dfs(pos - 1, cnt + t, lead && i == 0, limit && i == a[pos]); // 注意lead和limit的传递
*/
}
if(!limit && !lead) dp[pos][cnt] = res; // 根据需要, 进行记忆化存储
return res;
}
例题
dls动态规划中级课
数数3
- 求满足 存在 3 个连续数位单调递增的数字个数
ll dp[20][2][10][5];
ll dfs(int rem, int exist, int last, int inc) {
ll& ans = dp[rem][exist][last][inc];
if (ans != -1) return ans;
if (!rem) return exist;
ans = 0;
for (int i = 0; i <= 9; i ++) {
int new_inc = (i > last) ? min(3, inc + 1) : 1;
ans += dfs(rem - 1, exist | (new_inc == 3), i, new_inc);
}
return ans;
}
ll solve(ll x) {
x ++;
vector<int> d;
while (x) {
d.pb(x % 10);
x /= 10;
}
reverse(ALL(d));
int m = d.size();
ll ans = 0;
// 处理前导零
for (int i = 1; i <= m - 1; i ++) {
for (int j = 1; j <= 9; j++)
ans += dfs(i - 1, 0, j, 1);
}
int rem = 0, exist = 0, inc = 0, last = 0;
for (int i = 0; i < m; i++) {
for (int j = (i == 0) ? 1 : 0; j < d[i]; j++) {
int new_inc = (j > last) ? min(3, inc + 1) : 1;
ans += dfs(m - i - 1, exist | (new_inc == 3), j, new_inc);
}
inc = (d[i] > last) ? min(3, inc + 1) : 1;
last = d[i];
exist |= (inc == 3);
}
return ans;
}
CF1560F2. Nearest Beautiful Number (hard version)
- 定义 k-美丽数 为数位中不同数位最多为 \(k\) 的数字。
- 求大于等于 \(n\) 的最小 k-美丽数。
这类问题核心：快速判断剩下的位是否能满足要求(new_cnt <= k)
vector<int> d;
int n, k;
int vis[11]; // 多组数据清空 vis[]，直接返回dfs不一定回溯
bool dfs(int x, bool larger, int cnt, int num) {
if (x == (int)d.size()) {
printf("%d\n", num);
return true;
}
else {
for (int i = larger ? 0 : d[x]; i <= 9; i ++) {
vis[i]++;
int new_cnt = cnt;
if (vis[i] == 1) new_cnt++;
if (new_cnt <= k && dfs(x + 1, larger | (i > d[x]), new_cnt, num * 10 + i))
return true;
vis[i]--;
}
}
return false;
}
void solve(int x) {
d.clear();
while (x) {
d.pb(x % 10);
x /= 10;
}
reverse(ALL(d));
dfs(0, 0, 0, 0);
}
不同位大于等于 \(k\) 最小数字求法
这里的核心代码就是 new_cnt + (int)d.size() - x - 1 >= k ，还要减 1 是因为当前位的贡献已经计算在了 new_cnt 里面。
vector<int> d;
int n, k;
int vis[11];
bool dfs(int x, bool larger, int cnt, int num) {
if (x == (int)d.size()) {
printf("%d\n", num);
return true;
}
else {
for (int i = larger ? 0 : d[x]; i <= 9; i ++) {
vis[i]++;
int new_cnt = cnt;
if (vis[i] == 1) new_cnt++;
if (new_cnt + (int)d.size() - x - 1 >= k && dfs(x + 1, larger | (i > d[x]), new_cnt, num * 10 + i))
return true;
vis[i]--;
}
}
return false;
}
void solve(int x) {
d.clear();
while (x) {
d.pb(x % 10);
x /= 10;
}
reverse(ALL(d));
while (1) {
if (dfs(0, 0, 0, 0)) break; // 当前位数搜不到就要扩大位数，否则 break
int m = d.size() + 1;
d.clear();
d.push_back(1); // 原来有 m 位，扩大为 m + 1 位，那么从最小的 1000000开始，有 m 个 0
for (int i = 0; i < m - 1; i ++) d.push_back(0);
}
}
数位背包入门——梦幻岛宝珠
思路
- 形如背包重量为 \(a * 2^x\) 的题目，可以用数位背包的方法来尝试解题
- 由高到低位考虑，\(f[i][j]\) 表示到第 \(i\) 为还剩 \(j\) 个 \(2^i\) 容量的最大价值。
- 由于重量的系数 和 物品个数限制，考虑到第 \(i\) 位时，后面的所有位加起来贡献到第 \(i\) 位的重量是有限的，所以直接和物品重量总数取
min - 然后注意细节和转移，由于状态定义为还剩xxx时的最大价值，所以要用 剩的多反而背包价值更大 去更新剩的少的价值，代码中是后缀 max
const int N = 2010;
ll f[N], g[N];
int n, W;
// f[i][j] 到第 i 位，还剩 j 个容量的最大价值
vector<PII> item[35];
void solve() {
for (int i = 0; i <= 31; i ++) item[i].clear();
int sum = 0; // 重量总数
for (int i = 0; i < n; i ++) {
int w, v;
re(w), re(v);
int lev = __builtin_ctz(w);
w >>= lev;
item[lev].pb({w, v});
sum += w;
}
for (int i = 0; i <= sum; i++) f[i] = -2e18;
f[0] = 0;
for (int i = 30; i >=0 ; i--) {
for (int j = 0; j <= sum; j++) g[j] = f[j], f[j] = -2e18; // 滚动数组
int d = W >> i & 1;
for (int j = 0; j <= sum; j ++) { // 不选物品，i->i+1 背包状态转移，容量 * 2 + d
f[min(sum, 2 * j + d)] = max(f[min(sum, 2 * j + d)], g[j]);
}
// 选物品，背包转移, f[i][j] = max(f[i][j], f[i - 1][j + w] + v);
// w <= j <= sum, 所以需要记录 f[i][j] 为后缀 f[][] 最大值, 因为剩的更多价值更大，剩的少的价值应该被更新掉。
for (int j = sum - 1; j >= 0; j--)
f[j] = max(f[j], f[j + 1]);
for (auto p: item[i]) {
for (int j = 0; j <= sum - p.first; j++) {
f[j] = max(f[j], f[j + p.first] + p.second);
}
}
}
printf("%lld\n", f[0]);
}
2020-CCPC长春-D, Meaningless Sequence
- 有个小结论然后无脑做，有个二项式定理，\((1+c)^k = \Sigma_i^k(c^i * \binom{k}{i})\)
const int N = 3010, mod = 1e9 + 7;
ll power[N];
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
string s;
cin >> s;
int c, n = s.size();
re(c);
power[0] = 1;
for (int i = 1; i <= N - 10; i++)
power[i] = power[i - 1] * (c + 1) % mod;
ll pre = 1, ans = 0;
for (int i = 0; i < n; i ++) {
if (s[i] == '0') continue;
ans = (ans + pre * power[n - i - 1] % mod) % mod;
pre = pre * c % mod;
}
ans += pre;
printf("%lld\n", ans % mod);
// fclose(stdin);
// fclose(stdout);
return 0;
}
2020-ICPC济南-L, Bit Sequence
待补
标签：cnt,return,int,ll,---,dp,数位,DP,inc From： https://www.cnblogs.com/Roshin/p/remake_digital_DP.html