题解 P1063 【能量项链】

P1063 题解

这题建议在做完P1880 石子合并之后再做,思路其实和这题差不多


思路

这是一道经典的区间动规题,对于这种题我们一般用记搜解决(其实是因为刷表法过于抽象$\dots$ )

首先是珠子的处理,这里有一个问题:前一颗珠子的头标记后一颗珠子的尾标记,在DP时要特别注意这一点。另外一个问题就是珠子是成环状的,这样的环我们要使用拆成链后复制一遍接在环尾的方法,看代码:

1
2
3
4
5
6
7
8
//由于前一颗珠子的头标记是后一颗珠子的尾标记,
//因此我们可以用a数组直接同时存储当前竹子的头标记和上一颗珠子的尾标记
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i]; //复制一遍接在环尾
}
a[2*n+1]=a[1]; //最后一颗珠子的尾标记

接下来是DP的部分,DP的思想其实就是:(为了方便,这里用head[x]和tail[x]来代指x的头标记和尾标记(就是原数组中的a[x]和a[x+1])

设分界点为m,则合成l到r的总收益$=$合成head[l]到tail[m-1]的总收益(因为要使l和m接触)$+$合成head[m+1]到tail[r]的总收益 (因为要使m和r接触)$+$head[l]$\times$tail[m]$\times$tail[r] (再合并l和r)

画成图就是这样子:

当然,如果区间只有2项,则只能在l处合并,因此其总收益$=$head[l]$\times$tail[l]$\times$tail[r]

接下来就可以给出DP代码了:

1
2
3
4
5
6
7
8
9
10
11
12
13
//f为记忆化数组
int dp(int l,int r)
{
int ans=0;
if(f[l][r]!=0) return f[l][r];
if(l==r-1) return a[l]*a[r]*a[r+1];//边界(只有2项)
for(int k=l;k<r;k++)//枚举分界点
{
//注:a[x+1]就是tail[x]
ans=max(ans,dp(l,k)+dp(k+1,r)+a[l]*a[k+1]*a[r+1]);//更新答案
}
return f[l][r]=ans;//返回并记忆化
}

由于环拆成链后一共有n种可能的开头,所以需要n次DP计算出答案

代码:

1
2
3
4
5
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,dp(i,i+n-1));//head[i]到tail[i+n]就是a[i]到a[i+n-1]
}

关于时间复杂度

这题的时间复杂度很多人认为是$O(n^4)$,会超时,但其实并不是这样。这个算法的实际复杂度其实是$O(n^3)$。

为什么呢?因为在执行下一次DP时,上一次DP计算出的值是可以直接使用的。

让我们模拟一下算法执行的过程:(设n=5)

第一次DP时,要计算$n^2$个值,如图所示:(图中的绿色部分)

TIM截图20191024215559.png

这时,需要计算$n^2$个值,每个值需要$O(n)$的时间去计算,因此第一次DP的总复杂度为$O(n^3)$。

第二次DP时,图形变成了这样:

TIM截图20191024220023.png

这时,图中的黄色部分是已经计算好的值,可以直接使用,只有红色部分需要计算,而这样的格子一共有$2n-1$个,因此第二次DP只需要$O(n^2)$的时间去计算,第3~n次DP同理。

所以,整个算法的时间复杂度为$O(n^3+n(2n-1)\times n)=O(n^3)$。

(话说我好像是唯一一篇有时间复杂度分析的题解…)

代码

关键部分的注释之前已经给过了,这里就不给了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=201;
int f[maxn][maxn];
int n,a[maxn];
int dp(int l,int r)
{
int ans=0;
if(f[l][r]!=0) return f[l][r];
if(l==r-1) return a[l]*a[r]*a[r+1];
for(int k=l;k<r;k++)
{
ans=max(ans,dp(l,k)+dp(k+1,r)+a[l]*a[k+1]*a[r+1]);
}
return f[l][r]=ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}
a[2*n+1]=a[1];
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,dp(i,i+n-1));
}
cout<<ans<<endl;
return 0;
}

欢迎来到博客

文章作者: 1379号监听员
文章链接: https://listener1379.site/2019/题解-P1063-【能量项链】/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 1379号监听站
支付宝打赏
微信打赏