Comment

Huhu_Miao: 2025-05-21 10:00:30

/**
 *    author:  Huhu_Miao
 *    created: 2025.5.21 09:47:57 (UTC+8)
 *    O(n^3 k^2)，可过。
**/
#include<iostream>
#include<algorithm>

using u64 = unsigned long long;

constexpr int N = 21;
//From the i-th element to the j-th element of the array, k multiplication signs are used.
u64 dp[N][N][N]; 

void solve(){
	int n , k_max ; std::cin >> n >> k_max;
	for(int i = 1 ; i <= n ; i++) std::cin >> dp[i][i][0];
	for(int len = 2 ; len <= n ; len++){
		for(int i = 1 ; i <= n - len + 1; i++){
			int j = i + len - 1;
			for(int k = 0 ; k <= std::min(len - 1 , k_max) ; k++){
				u64 max = 0;
				//+ 
				for(int pivot = i ; pivot < j ; pivot++){
					for(int k1 = 0 ; k1 <= std::min(k , pivot - i + 1) ; k1++){
						int k2 = k - k1;
						max = std::max(max , dp[i][pivot][k1] + dp[pivot + 1][j][k2]);
					}
				}
				//*
				if(k != 0){
					for(int pivot = i ; pivot < j ; pivot++){
						for(int k1 = 0 ; k1 <= std::min(k - 1 , pivot - i) ; k1++){
							int k2 = k - k1 - 1;
							max = std::max(max , dp[i][pivot][k1] * dp[pivot + 1][j][k2]);
						}
					}
				}
				
				dp[i][j][k] = max;
			}
		}
	}

	std::cout << dp[1][n][k_max] << '\n';	
}

int main(){
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
	int T; std::cin>>T;
	while(T--) solve();
	return 0;
}

71123140焦博宇: 2025-05-15 11:33:34

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<climits>
#include<iomanip>
using namespace std;

int x[25],sum[25][25];
long long ans[25][25];

int main()
{
	int M;
	cin >> M;
	for (int i = 1; i <= M; i++)
	{
		int N, K;
		cin >> N >> K;
		for (int i = 1; i <= N; i++)
			cin >> x[i];
		for (int j = 0; j <= N - 1; j++)
			for (int i = 1; i <= N - j; i++)
			{
				if (j == 0)
					sum[i][i] = x[i];
				else
					sum[i][i + j] = sum[i][i + j - 1] + x[i + j];
			}
		for (int i = 1; i <= N; i++)
			ans[0][i] = sum[1][i];
		for (int i = 1; i <= K; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				if (j < i)continue;
				ans[i][j] = INT_MIN;
				for (int k = i; k <= j; k++)
				{
					ans[i][j] = max(ans[i][j], ans[i - 1][k] * sum[k + 1][j]);
				}
			}
		}
		cout << ans[K][N] << endl;
	}
	return 0;
}

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;
}