刷题记录:牛客NC16670能量项链
传送门:牛客
题目描述:
题目较长,此处省略
输入:
4
2 3 5 10
输出:
710
本题应该是一道链 + + +区间dp的题目.对于链,大家应该都不陌生,复制一遍即可,此处不在赘述
对于区间dp,本题和合并石子有点类似
我们可以使用
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]来记录区间
[
i
,
j
]
[i,j]
[i,j]合并完的最大值,那么显然的由区间dp,我们可以枚举区间
[
i
,
j
]
[i,j]
[i,j]直接的每一个位置.然后使用
d
p
[
i
]
[
j
]
=
m
a
x
(
d
p
[
i
]
[
k
]
+
d
p
[
k
+
1
]
[
j
]
+
n
o
d
e
[
l
]
.
l
∗
n
o
d
e
[
k
]
.
r
∗
n
o
d
e
[
r
]
.
r
)
dp[i][j]=max(dp[i][k]+dp[k+1][j]+node[l].l*node[k].r*node[r].r)
dp[i][j]=max(dp[i][k]+dp[k+1][j]+node[l].l∗node[k].r∗node[r].r)进行转移即可
下面是具体的代码部分:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n;
struct Node{
int l,r;
}node[maxn];
int dp[200][200];
int main() {
n=read();
for(int i=1;i<=n;i++) {
node[i].l=read();
}
node[n].r=node[1].l;
for(int i=1;i<n;i++) {
node[i].r=node[i+1].l;
node[i+n].l=node[i].l;
node[i+n].r=node[i].r;
}
for(int len=2;len<=n;len++) {
for(int l=1;l+len-1<=2*n-1;l++) {
int r=l+len-1;
for(int k=l;k<r;k++) {
dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+node[l].l*node[k].r*node[r].r);
}
}
}
int ans=-inf;
for(int i=1;i<=n;i++) {
ans=max(ans,dp[i][i+n-1]);
}
cout<<ans<<endl;
return 0;
}
相关文章
- Docker实践:Docker报错及相关问题记录
- 刷题记录:牛客NC24141[USACO 2011 Dec G]Grass Planting
- 【刷题记录⑧】Java工程师丨字节面试真题(二)
- 刷题记录:牛客NC216012Let‘s Play Curling
- 刷题记录:牛客NC13822Keep In Line
- 刷题记录:牛客NC15029吐泡泡
- 刷题记录:牛客NC16783[NOIP1998]拼数
- 刷题记录:NC16692[NOIP2001]求先序排列
- 刷题记录:牛客NC207028第k小数
- 刷题记录:牛客NC19784Shopping
- 刷题记录:牛客NC50965Largest Rectangle in a Histogram
- 刷题记录:牛客NC24724[USACO 2010 Feb S]Chocolate Eating
- 刷题记录:牛客NC25080[USACO 2007 Ope S]Catch That Cow
- 刷题记录:牛客NC19975[HAOI2008]移动玩具
- 刷题记录:牛客NC14698模拟战役
- 刷题记录:牛客NC14685加边的无向图
- 刷题记录:牛客NC16645[NOIP2007]矩阵取数游戏
- 刷题记录:牛客NC23413小A买彩票
- 刷题记录:牛客NC16886[NOI2001]炮兵阵地
- 刷题记录:牛客NC20273[SCOI2009]粉刷匠
- 刷题记录:牛客NC20568[SCOI2012]滑雪与时间胶囊
- 刷题记录:牛客NC26253小石的妹子
- 刷题记录:牛客NC20284[SCOI2011]糖果 tarjan+差分约束+拓扑排序
- 刷题记录:NC24587Watering the Fields