能量项链

C++ 解法, 执行用时: 4ms, 内存消耗: 540KB, 提交时间: 2022-04-05

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int N=2*105;
int n;
int a[N],dp[N][N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int len=1;len<n;len++){
        for(int i=0;i<2*n-len;i++){
            int j=i+len;
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],
               (dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1])%mod);
            }
        }
    }
    int res=0;
    for(int i=0;i<n;i++)    res=max(res,dp[i][i+n-1]);
    cout<<res<<endl;
     //for(int i=0;i<n;i++)    cout<<dp[i][i+n-1]<<" ";
    return 0;
}

C 解法, 执行用时: 5ms, 内存消耗: 432KB, 提交时间: 2022-06-22

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int start[2 * n + 1];
    for (int i = 0; i < n; i++) {
        scanf("%d", &start[i]);
        start[i+n] = start[i];
    }
    start[2 * n] = start[0];
    
    int **dp = (int **)malloc(sizeof(int *) * 2 * n);
    for (int i = 0; i < 2 * n; i++) {
        dp[i] = (int *)malloc(sizeof(int) * n);

        memset(dp[i], 0, sizeof(int) * n);
    }
    
    int maxPower = 0;
    for (int d = 1; d < n; d++) {
        for (int i = 0; i < 2 * n - d; i++) {
            for (int k = 0; k < d; k++) {
                dp[i][d] = max(dp[i][d], 
                               (dp[i][k] + dp[i+k+1][d-k-1] + start[i] * start[i+k+1] * start[i+d+1]) % 1000000007);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        maxPower = max(maxPower, dp[i][n-1]);
    }
    
    printf("%d", maxPower);
    
    for (int i = 0; i < 2 * n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return 0;
}

C++ 解法, 执行用时: 5ms, 内存消耗: 548KB, 提交时间: 2022-08-06

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int N=2*105;
int n;
int a[N],dp[N][N];
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		a[i+n]=a[i];
	}
	for(int len=1;len<n;len++)
	{
		for(int i=0;i<2*n-len;i++)
		{
			int j=i+len;
			for(int k=i;k<j;k++)
			{
				dp[i][j]=max(dp[i][j],(dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1])%mod);
			}
		}
	}
	int res=0;
	for(int i=0;i<n;i++)
	res=max(res,dp[i][i+n-1]);
	cout<<res<<endl;
	return 0;
}

C++ 解法, 执行用时: 5ms, 内存消耗: 552KB, 提交时间: 2022-08-06

#include <bits/stdc++.h>
using namespace std;
//typedef long long LL;
const int mod=1e9+7;
const int N=2*105;
int n;
int a[N],dp[N][N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int len=1;len<n;len++){
        for(int i=0;i<2*n-len;i++){
            int j=i+len;
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],
               (dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1])%mod);
            }
        }
    }
    int res=0;
    for(int i=0;i<n;i++)    res=max(res,dp[i][i+n-1]);
    cout<<res<<endl;
     //for(int i=0;i<n;i++)    cout<<dp[i][i+n-1]<<" ";
    return 0;
}
// #include <iostream>
// using namespace std;

// const int N=210;
// int w[N],dp[N][N],mod=1e9+7;

// int main(){
//     int n;
//     cin>>n;
//     for(int i=0;i<n;i++){
//         cin>>w[i];
//         w[i+n]=w[i];//构成环型
//     }
//     for(int len=3;len<=n+1;len++){
//         for(int l=1;l<=2*n+1-len;l++){
//             int r=l+len-1;
//             for(int k=l+1;k<r;k++){
//                 dp[l][r]=max(dp[l][r]%mod,(dp[l][k]+dp[k][r]+w[l]*w[k]*w[r])%mod);
//             }
//         }
//     }
//     int res=0;
//     for(int i=1;i<=n;i++) res=max(res,dp[i][i+n]);
//     cout<<res;
    
//     return 0;
// }

C++ 解法, 执行用时: 5ms, 内存消耗: 552KB, 提交时间: 2022-05-15

#include <bits/stdc++.h>
using namespace std;
//typedef long long LL;
const int mod=1e9+7;
const int N=2*105;
int n;
int a[N],dp[N][N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    for(int len=1;len<n;len++){
        for(int i=0;i<2*n-len;i++){
            int j=i+len;
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],
               (dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1])%mod);
            }
        }
    }
    int res=0;
    for(int i=0;i<n;i++)    res=max(res,dp[i][i+n-1]);
    cout<<res<<endl;
     //for(int i=0;i<n;i++)    cout<<dp[i][i+n-1]<<" ";
    return 0;
}

详情