【动态规划】【记忆化搜索】1017 乘积最大 2000年NOIP全国联赛普及组NOIP全国联赛提高组

跟CODEVS 3415没有什么区别，也不用高精度。

http://www.cnblogs.com/autsky-jadek/p/4055184.html

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 ll n,dp[41][41][7],ans=-10000000000000;
 8 int m,wei,len;
 9 const ll Base[]=
10 {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,
11 10000000000,100000000000,1000000000000,10000000000000,100000000000000,
12 1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
13 ll Get_Part(const int &l,const int &r) {return n%Base[wei-l+1]/Base[wei-r];}
14 ll f(int sta,int end,int now)
15 {
16     if(dp[sta][end][now]!=-1) return dp[sta][end][now];
17     ll res=-10000000000000;
18     if(now==2) res=max(res,Get_Part(sta,end)*f(end+1,wei,now-1));
19     else
20       for(int i=end+1;i<=wei-(now-2);i++)
21         res=max(res,Get_Part(sta,end)*f(end+1,i,now-1));
22     return dp[sta][end][now]=res;
23 }
24 int main()
25 {
26     scanf("%d%d",&wei,&m); cin>>n; m++;
27     if(m==1)
28       {
29         printf("%lld
",n);
30         return 0;
31       }
32     memset(dp,-1,sizeof(dp));
33     for(int i=1;i<=wei-m+1;i++)
34       dp[wei-i+1][wei][1]=Get_Part(wei-i+1,wei);
35     for(int i=1;i<=wei-m+1;i++)
36       ans=max(ans,f(1,i,m));
37     printf("%lld
",ans);
38     return 0;
39 }