Login
Register
Problem list
Online status
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
#include
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
#include
#include
#include
#include
#include
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
#include
#include
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
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
222186
:
2022-09-29 16:17:48
#include
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; }
Post Your Comment