[KDOI-10]商店砍价
考虑dp，钦定全用操作 \(1\)，容易由 \(v_i\le 10^5\) 发现只有剩下的数位小于 \(6\) 时用操作 \(2\) 才更优。于是我们设 \(f_{i,j}\) 为考虑完第 \(i\) 位剩下 \(j\) 个数用操作 \(2\) 能减小的最大代价，并从高位向低位考虑。
转移方程很显然，选或不选用操作 \(2\) 能减小的代价取最大值，对于数位 \(x\) 剩下 \(j\) 位，因为是从低到高枚举用操作 \(2\) 即保留这一位的代价为 \(x\times 10^{j-1}\)。所以转移方程为 $$f_{i,j}=\max(f_{i+1,j},f_{i+1,j-1}+v_i-a_i\times 10^{j-1})$$ \(a_i\) 为输入数从左向右数第 \(i\) 位。
Code:
#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define int long long
#define ull unsigned long long
#define fst first
#define snd second
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-6;
inline bool pts(char ch){return ch>=48&&ch<=57;}
inline int read(){bool f=0;int x=0;char ch;ch=gt();while(!pts(ch)&&ch!=EOF){if(ch=='-')f=1;ch=gt();}while(pts(ch)){x*=10;x+=(ch-48);ch=gt();}if(f)return -x;else return x;
}
template<class T>
inline void print(T x){char s[114];int top=0;if(x<0)pt('-');do{top++;if(x>=0)s[top]=(x%10)+48;else s[top]=(-(x%10)+48);x/=10;}while(x);while(top){pt(s[top]);top--;}
}
int f[100005][10];
int v[10];
//|n|>6时1一定优，设f[i][j]为考虑到第i位利用策略二答案减小的值
void solve(){memset(f,-1,sizeof(f));string s;cin>>s;int len=s.size();s=' '+s;int sum=0;for(int i=1;i<=9;i++)v[i]=read();f[len+1][0]=0;for(int i=len;i>=1;i--){//假设全部考虑完，反着找sum+=v[s[i]-'0'];f[i][0]=f[i+1][0];for(int j=1;j<=6;j++){f[i][j]=max(f[i][j],f[i+1][j]);f[i][j]=max(f[i+1][j],f[i+1][j-1]+v[s[i]-'0']-(s[i]-'0')*(int)powl(10,j-1));}}int maxn=-1;for(int j=1;j<=6;j++)maxn=max(maxn,f[1][j]);cout<<min(sum,sum-maxn)<<'\n';
}
signed main(){int c=read(),T=read();while(T--)solve();return 0;
}
