自动搬运

查看原文

来自洛谷，原作者为

	Fated_Shadow 银碗盛雪，明月藏鹭，白马入芦花

搬运于2025-08-24 22:42:37，当前版本为作者最后更新于2023-01-01 21:36:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门，同时，到博客使用更好。

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$ 次，那么：

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 可以自己去试一试）。

#include<iostream>
#include<cstdio>
using namespace std;

const int N = 30,M = 110;
long long dp[N][M][M],ans[N][2],num;//十年 oi 两行泪，不开 long long ___
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，请联系本蒟蒻，一定改正。

（没有也可以点个赞或关注啊）。