首页 > 代码库 > wikioi 1017 乘积最大
wikioi 1017 乘积最大
dp[i][j]=max(dp[i][j],dp[t][k-1]*mapn[t+1][i]);
dp[i][j]代表从0-i之间有j个乘号,mapn[i][j]表示第i位到第j位的数究竟是多少
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <ctime> 5 #include <iostream> 6 #include <algorithm> 7 #include <set> 8 #include <vector> 9 #include <sstream>10 #include <queue>11 #include <typeinfo>12 typedef long long ll;13 using namespace std;14 char str[10010];15 ll mapn[50][50];16 int main()17 {18 int n,m;19 cin>>n>>m;20 cin>>str;21 for(int i=0;i<n;i++)22 {23 int mm;24 mm=0;25 for(int j=i;j<n;j++)26 {27 mm=mm*10+str[j]-‘0‘;28 mapn[i][j]=mm;29 }30 }31 ll dp[51][10];32 memset(dp,0,sizeof(dp));33 for(int i=0;i<n;i++)34 dp[i][0]=mapn[0][i];35 for(int i=0;i<n;i++)36 {37 for(int k=1;k<=m;k++)38 {39 for(int t=0;t<i;t++)40 {41 dp[i][k]=max(dp[i][k],dp[t][k-1]*mapn[t+1][i]);42 }43 }44 }45 cout<<dp[n-1][m]<<endl;46 return 0;47 }
wikioi 1017 乘积最大
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。