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

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

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

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 ll n,dp[][][],ans=-;

 int m,wei,len;

 const ll Base[]=

 {,,,,,,,,,,

 ,,,,,

 ,,,};

 ll Get_Part(const int &l,const int &r) {return n%Base[wei-l+]/Base[wei-r];}

 ll f(int sta,int end,int now)

 {

     if(dp[sta][end][now]!=-) return dp[sta][end][now];

     ll res=-;

     if(now==) res=max(res,Get_Part(sta,end)*f(end+,wei,now-));

     else

       for(int i=end+;i<=wei-(now-);i++)

         res=max(res,Get_Part(sta,end)*f(end+,i,now-));

     return dp[sta][end][now]=res;

 }

 int main()

 {

     scanf("%d%d",&wei,&m); cin>>n; m++;

     if(m==)

       {

         printf("%lld\n",n);

         return ;

       }

     memset(dp,-,sizeof(dp));

     for(int i=;i<=wei-m+;i++)

       dp[wei-i+][wei][]=Get_Part(wei-i+,wei);

     for(int i=;i<=wei-m+;i++)

       ans=max(ans,f(,i,m));

     printf("%lld\n",ans);

     return ;

 }