P8801 题解

· · 题解

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

Introduction

对于这道 数位 dp 偏简单例题——

（怎么看出来的？标签，处理数较大，处理部分按数位进行，是数位 dp 罢。）

楼下大佬用递归搜索 dp 或贪心暴力切题，本人秉着应有尽有的原则，为社区着想 （蹭估值） 地交了一篇递推写法的 dp。

Solution

先将输入的数字按位处理好后，应该建立状态转移方程。

因为本题数据太水了（bushi，蒟蒻懒得想，故构造了一个三维数组 dp_{i,k,p}，其中：

那么依照背包问题的处理方式，假设将当前位数字 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，请联系本蒟蒻，一定改正。

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