首页 > 代码库 > 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 最小和