首页 > 代码库 > 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 乘积最大