foreword
题目传送门，同时，到博客使用更好。
Introduction
对于这道 数位 dp 偏简单例题——
（怎么看出来的？标签，处理数较大，处理部分按数位进行，是数位 dp 罢。）
楼下大佬用递归搜索 dp 或贪心暴力切题，本人秉着应有尽有的原则，为社区着想 （蹭估值） 地交了一篇递推写法的 dp。
Solution
先将输入的数字按位处理好后，应该建立状态转移方程。
因为本题数据太水了（bushi，蒟蒻懒得想，故构造了一个三维数组 $dp_{i,k,p}$，其中：
- $i$ 表示已经推到了第 $i$ 位（从低位向高位）。
- $k$ 表示还剩下 $j$ 次 操作 $1$ 的次数。
- $p$ 则表示还剩下 $k$ 次操作 $2$ 的次数。
那么依照背包问题的处理方式，假设将当前位数字 $x$ 变换为 $y$，需操作 $1$ 共 $a$ 次，操作 $2$ 共 $b$ 次，那么：
1
2
| dp[i][k][p] = max(dp[i][k][p],dp[i - 1][k - a][p] + sum);
dp[i][k][p] = max(dp[i][k][p],dp[i - 1][k][p - b] + sum);
|
(此时请注意 $j - a$ 与 $k - b$ 是否大于等于 $0$，其中 $sum$ 表示 pow(10,i - 1) * y。)
然后在将 $y$ 枚举：for（y : x ~ 9)。（为什么不从 $x + 1$ 开始呢，因为即使预处理过了，但随着低位的递推，那么 $x$ 位也应该有所更替，蒟蒻就在这里写挂了。）
通过动态规划递推得到的数组，按照其定义，只用输出 $dp_{[\text{数的长度}][\text{操作 }1\text{ 次数}][\text{操作 }2\text{ 次数}]}$ 即可。
依照贪心思想，那如果执行操作 $2$，则 $y$ 会递减，那只有将 $y$ 变化为 $9$ 才是当前最优解，否则当前的答案不是最优解，可以直接舍去。
（代码中未给出优化，想要再调时间的 dalao 可以自己去试一试）。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<iostream>
#include<cstdio>
using namespace std;
const int N = 30,M = 110;
long long dp[N][M][M],ans[N][2],num;
int n,m,q[N],len = 0;
long long turn(long long a,long long b)
{
long long s = 1;
while(b)
{
if(b & 1) s *= a;
a *= a;
b >>= 1;
}
return s;
}
void deal()
{
memset(dp,0,sizeof dp);
for(int i = 1;i <= len;++ i)
{
long long sum = q[i] * turn(10,i - 1);
for(int k = 0;k <= n;++ k)
dp[i][k][0] = dp[i - 1][k][0] + sum;
for(int p = 0;p <= m;++ p)
dp[i][0][p] = dp[i - 1][0][p] + sum;
}
}
void solve(long long x)
{
memset(q,0,sizeof q);
while(x) q[++ len] = x % 10,x /= 10;
deal();
for(int i = 1;i <= len;++ i)
{
for(int j = q[i];j <= 9;++ j)
{
int a = j - q[i],b = q[i] + 10 - j;
long long sum = j * turn(10,i - 1);
for(int k = 0;k <= n;++ k)
for(int p = 0;p <= m;++ p)
{
if(k >= a) dp[i][k][p] = max(dp[i][k][p],dp[i - 1][k - a][p] + sum);
if(p >= b) dp[i][k][p] = max(dp[i][k][p],dp[i - 1][k][p - b] + sum);
}
}
}
return ;
}
int main()
{
scanf("%lld%d%d",&num,&n,&m);
solve(num);
printf("%lld",dp[len][n][m]);
return 0;
}
|
Afterword
第一次写 tj，如有 bug 或 hack，请联系本蒟蒻，一定改正。
（没有也可以点个赞或关注啊）。