【动态规划】P11188 「KDOI-10」商店砍价|普及+

本文涉及知识点

C++动态规划

P11188 「KDOI-10」商店砍价

题目背景

English Statement. You must submit your code at the Chinese version of the statement.

您可以点击 这里 下载本场比赛的选手文件。

You can click here to download all tasks and examples of the contest.

密码 / Password：rAnHoUyaSuoBaoMimaNijuEdefAngsHa2)2$1)0(2@0!

本场比赛所有题目从标准输入读入数据，输出到标准输出。

题目描述

有一个正整数 $n$，保证其只由数字 $1\sim 9$ 构成。

你可以做任意多次如下操作：

• 选择 $n$ 的一个数位 $x$，花费 v x v_x vx​ 的代价删除它，注意，此时 $n$ 的数位个数会减少 $1$，$n$ 的值也会发生相应的变化；
• 或者，花费 $n$ 的代价把剩余的所有数位删除。

求把整个数删除的最小代价。

输入格式

从标准输入读入数据。

本题有多组测试数据。

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含一个正整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行一个正整数 $n$，表示这个数的初始值。
• 第二行九个正整数 v 1 , v 2 , … , v 9 v_1,v_2,\\dots,v_9 v1​,v2​,…,v9​，表示删除每个数位的代价。

输出格式

输出到标准输出。

对于每组测试数据：

• 输出一行一个正整数，表示最小代价。

输入输出样例 #1

输入 #1

0312310 10 10 10 10 10 10 10 10 11212 1 2 2 2 2 2 2 29876543211 2 3 4 5 6 7 8 9

输出 #1

21645

说明/提示

【样例 1 解释】

对于第一组测试数据，最优操作方案如下：

• 删除数位 $2$，代价为 $10$，此时 $n$ 变为 $13$；
• 删除数位 $3$，代价为 $10$，此时 $n$ 变为 $1$；
• 删除 $n$ 的剩余所有数位，代价为 $1$。

总代价为 $10+10+1=21$，可以证明，这是代价的最小值。

对于第二组测试数据，一种最优操作方案如下：

• 删除第一个数位 $1$，代价为 $2$，此时 $n$ 变为 $121$；
• 删除最后一个数位 $1$，代价为 $2$，此时 $n$ 变为 $12$；
• 删除数位 $2$，代价为 $1$，此时 $n$ 变为 $1$；
• 删除 $n$ 的剩余所有数位，代价为 $1$。

总代价为 $2+2+1+1=6$。

【样例 2】

见选手目录下的 bargain/bargain2.in 与 bargain/bargain2.ans。

这个样例满足测试点 $3\sim 6$ 的约束条件。

【样例 3】

见选手目录下的 bargain/bargain3.in 与 bargain/bargain3.ans。

这个样例满足测试点 $11$ 的约束条件。

【样例 4】

见选手目录下的 bargain/bargain4.in 与 bargain/bargain4.ans。

这个样例满足测试点 $17,18$ 的约束条件。

【样例 5】

见选手目录下的 bargain/bargain5.in 与 bargain/bargain5.ans。

这个样例满足测试点 $23\sim 25$ 的约束条件。

---

【数据范围】

对于全部的测试数据，保证：

• $1\le t\le 10$；
• 1 ≤ n < 1 0 1 0 5 1\\le n< 10^{10^5} 1≤n<10105；
• 对于任意 $1\le i\le 9$， 1 ≤ v i ≤ 1 0 5 1\\le v_i\\le 10^5 1≤vi​≤105；
• $n$ 由数字 $1\sim 9$ 构成。

测试点 $n<$ v i ≤ v_i\\le vi​≤ 特殊性质 $1$ $100$ 1 0 5 10^5 105 无 $2$ 1 0 3 10^3 103 1 0 5 10^5 105 无 $3\sim 6$ 1 0 18 10^{18} 1018 1 0 5 10^5 105 无 $7\sim 9$ 1 0 40 10^{40} 1040 1 0 5 10^5 105 无 $10$ 1 0 1 0 5 10^{10^5} 10105 1 0 5 10^5 105 $n$ 由至多一种数字构成 $11$ 1 0 1 0 5 10^{10^5} 10105 1 0 5 10^5 105 $n$ 由至多两种数字构成 $12,13$ 1 0 1 0 5 10^{10^5} 10105 1 0 5 10^5 105 $n$ 由至多三种数字构成 $14\sim 16$ 1 0 1 0 3 10^{10^3} 10103 1 0 5 10^5 105 v 1 = v 2 = v 3 = ⋯ = v 9 v_1=v_2=v_3=\\dots =v_9 v1​=v2​=v3​=⋯=v9​ $17,18$ 1 0 1 0 5 10^{10^5} 10105 1 0 5 10^5 105 v 1 = v 2 = v 3 = ⋯ = v 9 v_1=v_2=v_3=\\dots =v_9 v1​=v2​=v3​=⋯=v9​ $19,20$ 1 0 100 10^{100} 10100 $100$ 无 $21,22$ 1 0 1 0 3 10^{10^3} 10103 1 0 3 10^3 103 无 $23\sim 25$ 1 0 1 0 5 10^{10^5} 10105 1 0 5 10^5 105 无

动态规划

性质一：最后删除前，数位一定不超过5位。如果超过5位，直接删除的成本是：
x×1 0 i − 1 +y x\\times 10^{i-1}+y x×10i−1+y,i是位数,x是最高位。删除最高位，再删除的成本是 v x +y v_x+y vx​+y，本题 v x ≤1 0 5 v_x \\le10^5 vx​≤105，故i > 5时，删除最高位再删除时不劣解。
性质二：最后删除x,相当于节约$x各位的成本-x$，删除所有位的成本-$\max (节约的成本)$便是答案。

动态规划的状态表示

dp[n][j]表示处理完s的后n位，保留了j位节约的最大成本。$n\in [0,N],j\in [0,5]$。
空间复杂度: O(n)

动态规划的填表顺序

枚举前驱状态，和操作。n从0到N-1,j任意。

动态规划的转移方程

如果倒数第n各位数z不保留
dp[n+1][j] = dp[n][j]
如果保留：
dp[n+1][j+1]=dp[n][j]+z∗1 0 j − v z dp[n+1][j+1] = dp[n][j] + z*10^j - v_z dp[n+1][j+1]=dp[n][j]+z∗10j−vz​

动态规划的初始值

dp[0][0] ，其它LLONG_MIN/2。

动态规划的范围值

sum - max(dp.back()) 。sum是直接删除所有位的成本和。

代码

核心代码

#include #include #include #include#include#include#include#include#include#include#include#include #include#include#include #include #include#include#include#include#include #include using namespace std::chrono;using namespace std;template<class T1, class T2>std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;}template<class T1, class T2, class T3 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;}template<class T1, class T2, class T3, class T4 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;}template<class T1, class T2, class T3, class T4, class T5, class T6, class T7 >std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5, T6, T7>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);return in;}template<class T = int>vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;}template<class T = int>vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if (\'\\n\' == cin.get()) { break; }}return ret;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;}template<int N = 1\'000\'000>class COutBuff{public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = \'-\', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char puffer[N], * m_p;};template<int N = 1\'000\'000>class CInBuff{public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();while ((\'\\r\' == *S) || (\'\\n\' == *S) || (\' \' == *S)) { S++; }//忽略空格和回车ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == \'-\');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == \'-\');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;};class Solution {public:long long Ans(const string& s, vector<int>& v) {const int N = s.length();vector<long long > pre(6, LLONG_MIN / 2);pre[0] = 0;vector<int> p10 = { 1,10,100,1000,10\'000,100\'000 };for (int n = 0; n < N; n++) {const int z = s[N - 1 - n] - \'0\';auto cur = pre;//不保留for (int j = 0; j + 1 < 6; j++) {cur[j + 1] = max(cur[j + 1], v[z - 1] - p10[j] * z + pre[j]);}pre.swap(cur);}long long sum = 0;for (const auto& ch : s) {sum += v[ch - \'1\'];}return sum - *max_element(pre.begin(), pre.end());}};int main() {#ifdef _DEBUGfreopen(\"a.in\", \"r\", stdin);#endif // DEBUGios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff in; COutBuff ob;int c, t;cin >> c >> t;string s;for (int i = 0; i < t; i++) {cin >> s;auto v = Read<int>(9);#ifdef _DEBUG//printf(\"M=%d\", M);Out(s, \",s=\");Out(v, \",v=\");//Out(ss, \",ss=\");//Out(ope, \",ope=\");#endif // DEBUGauto res = Solution().Ans(s,v);cout << res << \"\\n\";}return 0;}

单元测试

TEST_METHOD(TestMlethod11){auto res = Solution().Ans(\"9\", vector<int>{ 1,1,1,1,1,1,1,1,1 });AssertEx(1LL, res);}TEST_METHOD(TestMlethod12){s = \"123\", v = { 10,10,10,10,10,10,10,10,10 };auto res = Solution().Ans(s, v);AssertEx(21LL, res);}TEST_METHOD(TestMlethod13){s = \"1121\", v = { 2,1,2,2,2,2,2,2,2 };auto res = Solution().Ans(s, v);AssertEx(6LL, res);}TEST_METHOD(TestMlethod14){s = \"987654321\", v = { 1,2,3,4,5,6,7,8,9 };auto res = Solution().Ans(s, v);AssertEx(45LL, res);}

扩展阅读

我想对大家说的话 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 如果程序是一条龙，那算法就是他的是睛 失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。