首页 > 代码库 > codevs 3415 最小和
codevs 3415 最小和
题目描述 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。
把一个n位的数字串划分成k部分
使得所有部分形成的数加起来最小
这是一个划分型dp呢?还是区间dp?
反正很好做
dp[i][j]表示把前 i 位数字划分成 j 段的最小值
需要三重循环来递推
codevs 3415 最小和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。