f(l,r,i)表示第i段截第l位到第r位时，当前已经得到的价格最小值，可以很显然地发现，这个是没有后效性的，因为对之后截得的段都不造成影响。

注意水彩笔数=1的特判。

递归枚举当前段的r求解(∵l是前一段的r+1)，因为很多状态重复，所以可以记忆化。

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int save[9][9][9],m,n,wei,ans=2147483647,len; 6 const int Base[]={
   1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}; 7 int Get_Part(const int &l,const int &r) {
   return n%Base[wei-l+1]/Base[wei-r];} 8 int f(int sta,int end,int now) 9 {10     if(save[sta][end][now]!=-1) return save[sta][end][now];11     int res=2147483647;12     if(now==2) res=min(res,Get_Part(sta,end)+f(end+1,wei,now-1));13     else14       for(int i=end+1;i<=wei-(now-2);i++)15         res=min(res,Get_Part(sta,end)+f(end+1,i,now-1));16     return save[sta][end][now]=res;17 }18 int main()19 {20     scanf("%d%d",&n,&m);21     if(m==1)22       {23           printf("%d\n",n);24           return 0;25       } int t=n;26     while(t) {wei++; t/=10;}27     memset(save,-1,sizeof(save));28     for(int i=1;i<=wei-m+1;i++)29       save[wei-i+1][wei][1]=Get_Part(wei-i+1,wei);30     for(int i=1;i<=wei-m+1;i++)31       ans=min(ans,f(1,i,m));32     printf("%d\n",ans);33     return 0;34 }