【動態規劃】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$ 的代價刪除它，注意，此時 $n$ 的數位個數會減少 $1$ ， $n$ 的值也會發生相應的變化；
或者，花費 $n$ 的代價把剩余的所有數位刪除。

求把整個數刪除的最小代價。

輸入格式

從標準輸入讀入數據。

本題有多組測試數據。

輸入的第一行包含一個正整數 $c$ ，表示測試點編號。 $c = 0$ 表示該測試點為樣例。

第二行包含一個正整數 $t$ ，表示測試數據組數。

對于每組測試數據：

第一行一個正整數 $n$ ，表示這個數的初始值。
第二行九個正整數 $v_1,v_2,\dots,v_9$ ，表示刪除每個數位的代價。

輸出格式

輸出到標準輸出。

對于每組測試數據：

輸出一行一個正整數，表示最小代價。

輸入輸出樣例 #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$ ，代價為 $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\le n< 10^{10^5}$ ；
對于任意 $1\le i\le 9$ ， $1\le v_i\le 10^5$ ；
$n$ 由數字 $1\sim 9$ 構成。

測試點	$n <$	$v_i\le$	特殊性質
$1$	$100$	$10^5$	無
$2$	$10^3$	$10^5$	無
$3\sim 6$	$10^{18}$	$10^5$	無
$7\sim 9$	$10^{40}$	$10^5$	無
$10$	$10^{10^5}$	$10^5$	$n$ 由至多一種數字構成
$11$	$10^{10^5}$	$10^5$	$n$ 由至多兩種數字構成
$12, 13$	$10^{10^5}$	$10^5$	$n$ 由至多三種數字構成
$14\sim 16$	$10^{10^3}$	$10^5$	$v_1=v_2=v_3=\dots =v_9$
$17, 18$	$10^{10^5}$	$10^5$	$v_1=v_2=v_3=\dots =v_9$
$19, 20$	$10^{100}$	$100$	無
$21, 22$	$10^{10^3}$	$10^3$	無
$23\sim 25$	$10^{10^5}$	$10^5$	無

動態規劃

性質一：最后刪除前，數位一定不超過5位。如果超過5位，直接刪除的成本是：
$x\times 10^{i-1}+y$ ,i是位數,x是最高位。刪除最高位，再刪除的成本是 $v_x+y$ ，本題 $v_x \le10^5$ ，故i > 5時，刪除最高位再刪除時不劣解。
性質二：最后刪除x,相當于節約 $x 各位的成本 ? x$ ，刪除所有位的成本- $\max(節約的成本)$ 便是答案。

動態規劃的狀態表示

dp[n][j]表示處理完s的后n位，保留了j位節約的最大成本。 $\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*10^j - v_z$

動態規劃的初始值

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

擴展閱讀

我想對大家說的話
工作中遇到的問題，可以按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
學習算法：按章節學習《喜缺全書算法冊》，大量的題目和測試用例，打包下載。重視操作
有效學習：明確的目標及時的反饋拉伸區（難度合適）專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛
失敗+反思=成功成功+反思=成功