P1063 题解

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

---

思路

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

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

//由于前一颗珠子的头标记是后一颗珠子的尾标记，
//因此我们可以用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代码了：

//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计算出答案

代码：

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$个值，如图所示：(图中的绿色部分)

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

第二次DP时，图形变成了这样：

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

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

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

代码

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

#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;
}

欢迎来到博客