做网站需要实名认证吗,网站导航栏 字体,wordpress 注册很慢,seo sem优化3415 最小和 链接#xff1a;http://codevs.cn/problem/3415/ CodeVS原创 时间限制: 1 s空间限制: 64000 KB题目描述 Description小浣熊松松来到文具店#xff0c;选择了K支自己喜欢的水彩笔#xff0c;并抄下了它们的价格。可是到结算时#xff0c;他发现自己抄价格时抄… 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%的数据K1 对于100%的数据数字串长度不超过8K数字串长度。 由于是松松来划分因此可以出现有前导0的价格或者价格就是0。 题解用f[i][k]表示用前i个数字组成K个价格的最小价格h[i][j]表示第i到j个数字组成的价格可以得到以下公式 f[i][k]min(f[j][k-1]h[j1][i],f[i][k]) #includeiostream
using namespace std;
string s;
int N;
int f[10][10],h[10][10];
int m(int st,int ed){int c1,ans0;for(int ied;ist;i--){ ans(s[i]-0)*c;c*10;}return ans;
}
int main(){cinsN;int maxx2*10e8;int ls.length();for(int i0;il;i)for(int j0;jl;j)h[i][j]m(i,j);for(int i0;il;i)for(int k1;kN;k){if(k1)f[i][k]h[0][i];else f[i][k]maxx;}for(int k2;kN;k)for(int i0;il;i)for(int jk-2;ji-1;j){f[i][k]min(f[j][k-1]h[j1][i],f[i][k]);}coutf[l-1][N]endl;
} 转载于:https://www.cnblogs.com/EdSheeran/p/7454826.html
