【动态规划】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 n n，保证其只由数字 1 ∼ 9 1\sim 9 1∼9 构成。

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

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

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

输入格式

从标准输入读入数据。

本题有多组测试数据。

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

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

对于每组测试数据：

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

输出格式

输出到标准输出。

对于每组测试数据：

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

输入输出样例 #1

输入 #1

0 3 123 10 10 10 10 10 10 10 10 10 1121 2 1 2 2 2 2 2 2 2 987654321 1 2 3 4 5 6 7 8 9 

输出 #1

21 6 45 

说明/提示

【样例 1 解释】

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

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

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

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

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

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

【样例 2】

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

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

【样例 3】

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

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

【样例 4】

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

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

【样例 5】

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

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

【数据范围】

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

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

动态规划

性质一：最后删除前，数位一定不超过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 x各位的成本-x x各位的成本−x，删除所有位的成本- max ⁡ ( 节约的成本 ) \max(节约的成本) max(节约的成本)便是答案。

动态规划的状态表示

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

动态规划的填表顺序

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

动态规划的转移方程

如果倒数第n各位数z不保留
dp[n+1][j] = dp[n][j]
如果保留：
d p [ n + 1 ] [ j + 1 ] = d p [ 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<iostream>#include<sstream>#include<vector>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<string>#include<algorithm>#include<functional>#include<queue>#include<stack>#include<iomanip>#include<numeric>#include<math.h>#include<climits>#include<assert.h>#include<cstring>#include<list>#include<array>#include<bitset>#include<chrono>usingnamespace std::chrono;usingnamespace std;template<classT1,classT2> std::istream&operator>>(std::istream& in, pair<T1, T2>& pr){ in >> pr.first >> pr.second;return in;}template<classT1,classT2,classT3> std::istream&operator>>(std::istream& in, tuple<T1, T2, T3>& t){ in >> get<0>(t)>> get<1>(t)>> get<2>(t);return in;}template<classT1,classT2,classT3,classT4> 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<classT1,classT2,classT3,classT4,classT5,classT6,classT7> 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<classT=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<classT=int> vector<T>ReadNotNum(){ vector<T> ret; T tmp;while(cin >> tmp){ ret.emplace_back(tmp);if('\n'== cin.get()){break;}}return ret;}template<classT=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>classCOutBuff{public:COutBuff(){ m_p = puffer;}template<classT>voidwrite(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();}voidwritestr(constchar* sz){strcpy(m_p, sz); m_p +=strlen(sz);AuotToFile();}inlinevoidwrite(char ch){*m_p++= ch;AuotToFile();}inlinevoidToFile(){fwrite(puffer,1, m_p - puffer,stdout); m_p = puffer;}~COutBuff(){ToFile();}private:inlinevoidAuotToFile(){if(m_p - puffer > N -100){ToFile();}}char puffer[N],* m_p;};template<int N =1'000'000>classCInBuff{public:inlineCInBuff(){}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();intx(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>>(longlong& val){FileToBuf();longlongx(0);intf(0);while(!isdigit(*S)) f |=(*S++=='-');while(isdigit(*S)) x =(x <<1)+(x <<3)+(*S++^48); val = f ?-x : x; S++;//忽略空格换行return*this;}template<classT1,classT2>inline CInBuff&operator>>(pair<T1, T2>& val){*this>> val.first >> val.second;return*this;}template<classT1,classT2,classT3>inline CInBuff&operator>>(tuple<T1, T2, T3>& val){*this>> get<0>(val)>> get<1>(val)>> get<2>(val);return*this;}template<classT1,classT2,classT3,classT4>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<classT=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<classT=int> vector<T>Read(int n){ vector<T>ret(n);for(int i =0; i < n; i++){*this>> ret[i];}return ret;}template<classT=int> vector<T>Read(){ vector<T> ret;*this>> ret;return ret;}private:inlinevoidFileToBuf(){constint 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;};classSolution{public:longlongAns(const string& s, vector<int>& v){constint N = s.length(); vector<longlong>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++){constint 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);}longlong sum =0;for(constauto& ch : s){ sum += v[ch -'1'];}return sum -*max_element(pre.begin(), pre.end());}};intmain(){#ifdef_DEBUGfreopen("a.in","r",stdin);#endif// DEBUG  ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff<> in; COutBuff<10'000'000> 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// DEBUG auto res =Solution().Ans(s,v); cout << res <<"\n";}return0;}

单元测试

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);}

扩展阅读

视频课程

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

测试环境

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