Comment

hanser414627925: 2024-05-29 21:52:31

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
	int m, n, k;
	cin >> m;
	long long max[20][20], data[20][20];
	for (int i = 0; i < m; i++) {
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < 20; j++) {
				max[i][j] = 0; data[i][j] = 0;

			}
		}
		cin >> n >> k;
		int* a = new int[n];
		for (int j = 0; j < n; j++) {
			cin >> a[j];
		}
		for (int j = 0; j < n; j++) {
			long long temp =0 ;
			for (int t = j; t < n; t++) {
				temp = temp + a[t];
				data[j][t] = temp;
			}
		}
		for (int j = 0; j < n; j++) {
			max[j][0] = data[0][j];
		}
		for (int j = 0; j < n; j++) {
			for (int w = 1; w <= j && w <= k; w++) {
				for (int t = 0; t < j; t++) {
					max[j][w]=(max[t][w-1]*data[t+1][j]>max[j][w]? max[t][w - 1] * data[t + 1][j] : max[j][w]);

				}
			}
		}
		cout << max[n - 1][k] << endl;
	}
	return 0;
}

Westbrook: 2024-05-29 20:08:27

注意空间开成21的，开成20的有个样例过不了

222186: 2022-09-29 16:19:22

#include <iostream>
using namespace std;

int N,K;
int a[21];
int dp[21][21] = {0};//dp[i][j]表示前i个数中有j个乘号时候所得到的最大值

void input(){
    scanf("%d %d",&N,&K);
    for(int i=1; i<=N; i++){
        scanf("%d",&a[i]);
    }
}

int sum(int start, int end){//为了求和
    int s = 0;
    for(int i=start; i<=end; i++){
        s += a[i];
    }
    return s;
}

void init_dp(){
    for(int i = 1; i<=N; i++){//j=0,表示没有乘号全是+
        dp[i][0] = sum(1,i);
    }
}

void solve(){
    init_dp();

    for(int i=2; i<=N; i++){//前i个数可以插入i-1个符号
        for(int j=1; j<=min(i-1,K); j++){//插入k个乘数符号，j在1到i个数里最多插i-1个
            for(int k=2; k<=i; k++){
                dp[i][j] = max(dp[i][j],dp[k-1][j-1]*sum(k,i));//关键的状态转移方程
            }
        }
    }

    cout << dp[N][K] << endl;
}

int main() {
    int M;
    cin >> M;

    for(int i=0; i<M; i++){
        input();
        solve();
    }
    return 0;
}

222186: 2022-09-29 16:17:48

#include <iostream>
using namespace std;
 
int sum(int a[], int start, int end){
	int s = 0;
	for(int i = start; i <= end; i++){
		s += a[i];
	}
	return s;
} 
 
int main(){
	int m;
	cin >> m;
	while(m--){
		int n, k;//n个数据，k个乘号
		cin >> n >> k;
		int a[21] = {0};
		long long dp[21][21] = {0}; //dp[i][j]表示前i个数中有j个乘号时，所得最大值
		for(int i = 1; i <=n ; i++){
			cin >> a[i];
		}
		for(int i = 1; i <= n; i++){//j=0表示没有*全是+ 
			dp[i][0] = sum(a, 1, i);
		}
		for(int i = 2; i <= n; i++){//前i个数可以插入i-1个符号 
			for(int j = 1; j <= min(i-1, k); j++){//插入k个乘数符号,j在1-i个数里最多只能插入i-1个
				for(int k = 2; k <= i; k++){//k为这个乘号的位置(1 2 3 …… k-1 k ……i)
					dp[i][j] = max(dp[i][j], dp[k-1][j-1] * (sum(a, k, i)));//从k处断开，后半部分用加号，前半部分继续递加入j-1个乘号 
				} 
			}
		}
		cout << dp[n][k] << endl;
		 
	}
	return 0;
}