题目描述
blablabla
样例
blablabla
算法1
(暴力枚举)
区间dp的板子题目吧
dp[l][r]表示区间l r 的最大能量
那么对于l r其中的一个k 有转移方程
dp[l][r] = max(dp[l][r],dp[l][k]+dp[k+1][r] + a[l]a[k+1]a[r+1])
后面加的这个式子具体就是看题目描述了 可以任选一个k自己模拟一下就有那个式子。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e2+10;
int a[maxn],dp[maxn][maxn];
int solve(int l,int r)// 这里采用递归的方法进行dp
{
int ans = dp[l][r];
if(ans) return ans;
else if(l==r) return 0;
else if(r==l+1) return a[l]*a[r]*a[r+1];
else
{
for(int k = l; k < r; k++)
{
ans = max(ans,solve(l,k)+solve(k+1,r)+a[l]*a[k+1]*a[r+1]);
}
}
return dp[l][r]=ans;
}
int main()
{
int n;
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
a[i+n] = a[i];
}
int ans = 0;
for(int i = 1; i <= n; i++)
{
ans = max(ans,solve(i,i+n-1));
}
printf("%d",ans);
}
用记忆化搜索是不是不容易出错