首页 > 代码库 > NYOJ - 整数划分(四)
NYOJ - 整数划分(四)
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=746
要求对一个n的整数插入m个乘号,求最大结果。
构造dp:dp[i][j]表示枚举至j时,插入i个乘号的状态。
那么dp[i][j]=dp[i-1][k]*sum(k+1,j)。
#include <iostream> #include <map> #include <algorithm> #include <vector> #include <string> #include <set> #include <cmath> #define LL long long int using namespace std; int n; LL ap[25][25]; LL dp[25][25]; int main() { int t; cin.sync_with_stdio(false); cin>>t; while(t--) { string s; int num; cin>>s>>num; for(int i=0;i<s.length();i++) { LL sum=0; for(int j=i;j<s.length();j++) { sum*=10; sum+=s[j]-‘0‘; ap[i][j]=sum; } } num--; int len=s.length(); for(int i=0;i<=num;i++) { for(int j=i;j<len;j++) { if(i==0) dp[i][j]=ap[0][j]; else { dp[i][j]=-1; for(int k=i-1;k<j;k++) dp[i][j]=max(dp[i][j],dp[i-1][k]*ap[k+1][j]); } } } LL ans=-1; for(int i=num;i<len;i++) ans=max(ans,dp[num][i]); cout<<ans<<endl; } return 0; }
NYOJ - 整数划分(四)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。