50分之P1018

幻蓝刀心 · 2019-07-13 17:06:00 · 个人记录

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000;
int n,m;
string s;
int a[maxn],f[maxn][maxn],g[maxn][maxn]; 
int get()
{
    char ch;int x=0;int p=1;
    ch=getchar();
    while(ch<'0' || ch>'9')
        ch=getchar();
    if(ch=='-')p=-1;
    while(ch>='0' && ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return p*x;
}
int got(int x,int y)
{
    int num=0;
    x--,y--;
    for(int i=x-1;i<y;i++)
      num=a[i]+num*10;
    return num;
}
int long long  dfs(int x,int y)
{
    if(!f[x][y])
    {
      long long mx=0;
      for(int l=y-1;l<x;l++)
      {
         if(dfs(l,y-1)*got(l+1,x)>mx)
           mx=dfs(l,y-1)*got(l+1,x);
      }
      f[x][y]=mx;
    }
    return f[x][y];
}

int main()
{
    n=get(),m=get();
    scanf("%s",&s);
    for(int i=0;i<n;i++)
      a[i]=s[i]-'0';
    for(int i=1;i<=n;i++)
      f[i][i]=got(1,i);
      cout<<dfs(n,m+1);
    //system("pause");
    return 0;
}