CodeVS/1017

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
乘积最大	★☆☆☆☆	答案正确	100	2015-1-24 20:14:11	无

题意

一串数字在中间添若干个乘号，问结果最大值。

题解

• DP，方程为：

显示/移除行号

    dp[1][cut][k]=max{dp[1][cut-length][k-1]*cut点处前length个数的乘积};//由于[1]和[k]维度的单调性可以略去以节省空间

代码

1017 .cpp代码已折叠 展开折叠内容

显示/移除行号 #include<cstdio> #include<algorithm> long long N,K; char a[100]={}; long long dp[100]={}; const long long getNum(const long long &_from,const long long &_to) { long long $t=0; for(long long i=_from;i<=_to;++i) { $t*=10; $t+=a[i]; } return $t; } int main() { scanf("%lld%lld\n",&N,&K); for(long long i=1;i<=N;++i) { scanf("%c",&a[i]); a[i]-='0'; dp[i]=getNum(1,i); } for(long long k=1;k<=K;++k) { for(long long cut=N;cut>=1;--cut) { dp[cut]=0; for(long long length=1;cut-length>0;++length) { dp[cut]=std::max(dp[cut],dp[cut-length]*getNum(cut-length+1,cut)); } } } printf("%lld\n",dp[N]); return 0; }