首页 > 代码库 > 【动态规划】【记忆化搜索】CODEVS 最小和 CodeVS原创
【动态规划】【记忆化搜索】CODEVS 最小和 CodeVS原创
f(l,r,i)表示第i段截第l位到第r位时，当前已经得到的价格最小值，可以很显然地发现，这个是没有后效性的，因为对之后截得的段都不造成影响。
注意水彩笔数=1的特判。
递归枚举当前段的r求解(∵l是前一段的r+1)，因为很多状态重复，所以可以记忆化。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 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 }
【动态规划】【记忆化搜索】CODEVS 最小和 CodeVS原创
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。