3415 最小和
链接:http://codevs.cn/problem/3415/
CodeVS原创
时间限制: 1 s
空间限制: 64000 KB
题目描述 Description
小浣熊松松来到文具店,选择了K支自己喜欢的水彩笔,并抄下了它们的价格。可是到结算时,他发现自己抄价格时抄得太密集,以至于所有价格连成了一个数字串(你可以假设价格都是正整数)。老板想和松松开个玩笑,于是对他说:“你可以把这个数字串分成K段,代表这K支笔的价格,然后把他们加起来,就是你要付给我的钱了。”当然,松松想尽可能省下钱去买《算法导论》,所以请你来帮忙算算,他最少需要付多少钱。
输入描述 Input Description
第一行包含一个整数N,代表松松抄下来的数字串。
第二行包含一个整数K,代表松松买了K支水彩笔。
输出描述 Output Description
输出仅一行,为松松买这些笔最少花的钱。
样例输入 Sample Input
79846
3
样例输出 Sample Output
133
数据范围及提示 Data Size & Hint
对于20%的数据,K=1;
对于100%的数据,数字串长度不超过8,K<=数字串长度。
由于是松松来划分,因此可以出现有前导0的价格,或者价格就是0。
题解:用f[i][k]表示用前i个数字组成K个价格的最小价格,h[i][j]表示第i到j个数字组成的价格;可以得到以下公式
f[i][k]=min(f[j][k-1]+h[j+1][i],f[i][k])
#include<iostream> using namespace std; string s; int N; int f[10][10],h[10][10]; int m(int st,int ed){ int c=1,ans=0; for(int i=ed;i>=st;i--){ ans+=(s[i]-'0')*c; c*=10; } return ans; } int main(){ cin>>s>>N; int maxx=2*10e8; int l=s.length(); for(int i=0;i<l;i++) for(int j=0;j<l;j++)h[i][j]=m(i,j); for(int i=0;i<l;i++) for(int k=1;k<=N;k++){ if(k==1)f[i][k]=h[0][i]; else f[i][k]=maxx; } for(int k=2;k<=N;k++) for(int i=0;i<l;i++) for(int j=k-2;j<=i-1;j++){ f[i][k]=min(f[j][k-1]+h[j+1][i],f[i][k]); } cout<<f[l-1][N]<<endl; }