试题 D: 最大数字
时间限制: 1.0s 内存限制: 256.0MB 本题总分:10 分
【问题描述】
给定一个正整数 N。你可以对 N 的任意一位数字执行任意次以下 2 种操
作:
1. 将该位数字加 1。如果该位数字已经是 9,加 1 之后变成 0。
2. 将该位数字减 1。如果该位数字已经是 0,减 1 之后变成 9。
你现在总共可以执行 1 号操作不超过 A 次,2 号操作不超过 B 次。
请问你最大可以将 N 变成多少?
【输入格式】
第一行包含 3 个整数:N, A, B。
【输出格式】
一个整数代表答案。
【样例输入】
123 1 2
【样例输出】
933
【样例说明】
对百位数字执行 2 次 2 号操作,对十位数字执行 1 次 1 号操作。
【评测用例规模与约定】
对于 30% 的数据,1 ≤ N ≤ 100; 0 ≤ A, B ≤ 10
试题 D: 最大数字 6
第十三届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组
对于 100% 的数据,1 ≤ N ≤ 1017; 0 ≤ A, B ≤ 100
动态规划
$f(i, j, k)$ 前 $i$ 个数字 用了 $j$ 加法, $k$ 次减法的最大值
决策:看最后一位怎么分配使其最大化
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long i64;
const int N = 20, M = 110;
int n, a , b;
int s[N];
string str;
i64 f[N][M][M];
int get(int x, int a, int b)
{
return ((x + a - b) % 10 + 10) % 10;
}
int main()
{
cin >> str >> a >> b;
for (auto x : str) s[ ++ n] = x - '0';
f[1][0][0] = s[1];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= a; j ++ )
for (int k = 0; k <= b; k ++ )
for (int x = 0; x <= j; x ++ )
for (int y = 0; y <= k; y ++ )
f[i][j][k] = max(f[i][j][k], f[i - 1][j - x][k - y] * 10 + get(s[i], x, y));
cout << f[n][a][b] << endl;
return 0;
}