P11188 「KDOI-10」商店砍价题目背景您可以点击 这里 下载本场比赛的选手文件。密码rAnHoUyaSuoBaoMimaNijuEdefAngsHa2)2$1)0(20!本场比赛所有题目从标准输入读入数据输出到标准输出。题目描述有一个正整数n nn保证其只由数字1 ∼ 9 1\sim 91∼9构成。你可以做任意多次如下操作选择n nn的一个数位x xx花费v x v_xvx的代价删除它注意此时n nn的数位个数会减少1 11n nn的值也会发生相应的变化或者花费n nn的代价把剩余的所有数位删除。求把整个数删除的最小代价。输入格式从标准输入读入数据。本题有多组测试数据。输入的第一行包含一个正整数c cc表示测试点编号。c 0 c0c0表示该测试点为样例。第二行包含一个正整数t tt表示测试数据组数。对于每组测试数据第一行一个正整数n nn表示这个数的初始值。第二行九个正整数v 1 , v 2 , … , v 9 v_1,v_2,\dots,v_9v1,v2,…,v9表示删除每个数位的代价。输出格式输出到标准输出。对于每组测试数据输出一行一个正整数表示最小代价。输入输出样例 #1输入 #10 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输出 #121 6 45说明/提示【样例 1 解释】对于第一组测试数据最优操作方案如下删除数位2 22代价为10 1010此时n nn变为13 1313删除数位3 33代价为10 1010此时n nn变为1 11删除n nn的剩余所有数位代价为1 11。总代价为10 10 1 21 10101211010121可以证明这是代价的最小值。对于第二组测试数据一种最优操作方案如下删除第一个数位1 11代价为2 22此时n nn变为121 121121删除最后一个数位1 11代价为2 22此时n nn变为12 1212删除数位2 22代价为1 11此时n nn变为1 11删除n nn的剩余所有数位代价为1 11。总代价为2 2 1 1 6 2211622116。【样例 2】见选手目录下的bargain/bargain2.in与bargain/bargain2.ans。这个样例满足测试点3 ∼ 6 3\sim 63∼6的约束条件。【样例 3】见选手目录下的bargain/bargain3.in与bargain/bargain3.ans。这个样例满足测试点11 1111的约束条件。【样例 4】见选手目录下的bargain/bargain4.in与bargain/bargain4.ans。这个样例满足测试点17 , 18 17,1817,18的约束条件。【样例 5】见选手目录下的bargain/bargain5.in与bargain/bargain5.ans。这个样例满足测试点23 ∼ 25 23\sim 2523∼25的约束条件。【数据范围】对于全部的测试数据保证1 ≤ t ≤ 10 1\le t\le 101≤t≤101 ≤ n 10 10 5 1\le n 10^{10^5}1≤n10105对于任意1 ≤ i ≤ 9 1\le i\le 91≤i≤91 ≤ v i ≤ 10 5 1\le v_i\le 10^51≤vi≤105n nn由数字1 ∼ 9 1\sim 91∼9构成。测试点n nnv i ≤ v_i\levi≤特殊性质1 11100 10010010 5 10^5105无2 2210 3 10^310310 5 10^5105无3 ∼ 6 3\sim 63∼610 18 10^{18}101810 5 10^5105无7 ∼ 9 7\sim 97∼910 40 10^{40}104010 5 10^5105无10 101010 10 5 10^{10^5}1010510 5 10^5105n nn由至多一种数字构成11 111110 10 5 10^{10^5}1010510 5 10^5105n nn由至多两种数字构成12 , 13 12,1312,1310 10 5 10^{10^5}1010510 5 10^5105n nn由至多三种数字构成14 ∼ 16 14\sim 1614∼1610 10 3 10^{10^3}1010310 5 10^5105v 1 v 2 v 3 ⋯ v 9 v_1v_2v_3\dots v_9v1v2v3⋯v917 , 18 17,1817,1810 10 5 10^{10^5}1010510 5 10^5105v 1 v 2 v 3 ⋯ v 9 v_1v_2v_3\dots v_9v1v2v3⋯v919 , 20 19,2019,2010 100 10^{100}10100100 100100无21 , 22 21,2221,2210 10 3 10^{10^3}1010310 3 10^3103无23 ∼ 25 23\sim 2523∼2510 10 5 10^{10^5}1010510 5 10^5105无C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;intc;intv[15],dp[100005][15],a[100005];intp10[15]{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};voidmian(){string n;cinn;intln.length();for(inti0;il;i)a[i1]n[i]-0;for(inti1;i9;i)cinv[i];memset(dp,0,sizeofdp);ints0;for(inti1;il;i)sv[a[i]];for(intil;i1;i--){for(intj1;jmin(9ll,l-i1);j){dp[i][j]max(dp[i1][j],dp[i1][j-1]v[a[i]]-p10[j-1]*a[i]);}}intans0;for(inti1;i9;i)ansmax(ans,dp[1][i]);couts-ansendl;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cinc;intt;cint;while(t--)mian();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
