记录编号	552845	评测结果	AAAAAAAAAA
题目名称	[NOIP 2000PJ]乘积最大	最终得分	100
用户昵称	Evolt	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2020-08-07 16:25:30	内存使用	13.75 MiB

#include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
#define N 41
#define K 7
using namespace std;
typedef unsigned long long ULL;
string s;
int n,e;
ULL f[N][N][K];
ULL num(int i,int j){
    ULL cnt = 0;
    for(int q = i;q <= j;++ q){
        cnt = (cnt << 1) + (cnt << 3) + s[q] - '0';
    }
    return cnt;
}
int main(){
    freopen("cjzd.in","r",stdin);
    freopen("cjzd.out","w",stdout);
    cin >> n >> e >> s;
    s = ' ' + s;
    for(int i = 1;i <= n;++ i){
        for(int j = 1;j <= n;++ j){
            f[i][j][0] = num(i , j);
           // cout << f[i][j][0] << ' ';
        }
       // printf("\n");
    }
    for(int k = 1;k <= e;++ k){
        for(int len = 2;len <= n;++ len){
            for(int j = 1;j + len <= n + 1;++ j){
                int end = j + len - 1;
                for(int i = j;i < end;++ i){
                    for(int q = 0;q < k&&q < len;++ q){
                        if(q < i - j + 1&&k - q - 1 < end - i + 1)f[j][end][k] = max(f[j][end][k] , f[j][i][q] * f[i + 1][end][k - q - 1]);
                    }
                }
            }
        }
    }
    cout << f[1][n][e] << endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}