题解 P1063 【能量项链】

NewErA · 2017-09-02 16:14:59 · 题解

第一次遇到区间dp，写个题解总结一下

区间dp能解决的问题就是通过小区间更新大区间，最后得出指定区间的最优解

个人认为，想要用区间dp解决问题，首先要确定一个大问题能够剖分成几个相同较小问题，且小问题很容易组合成大问题，从而从解决小问题逐渐解决大问题，体现的其实是分治的思想，只不过是通过dp用递推的方式解决了。比如floyd现在看来也属于区间dp 的一种。

本题应通过演算过程发现最终问题的解决可由两个相同规模较小的问题轻松地转化过来。（一般分治时只分成两个简化程序） 用f[l][r]表示以a[l]开头a[r]结尾的数串的最大和，如k为i,j之间任一节点，有f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]); 对l,r的定义自己一定要十分清晰，从而确定好循环的边界。

本题的小技巧：在环形问题中，可以选择(i+1)%n的方式，但也可以将n个元素复制一遍，变成2*n个元素，简化代码。

但也有问题随之而来，在更新时要将2*n个元素都更新，而不能只更新到前n个，否则访问到n+1~2n时会出错

附上代码

#include <bits/stdc++.h>
using namespace std;
int f[405][405];
int n,a[205]; 
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)  //***对环形问题的处理技巧***
    {
        cin >> a[i];
        a[n+i]=a[i];
    } 
    for(int i=2;i<=n+1;i++)
    {
        for(int l=1;l+i-1<=2*n;l++)  //如果采取了上述策略，一定要将2*n个点都更新 
        {
            int r=l+i-1;
            for(int k=l+1;k<=l+i-2;k++)
                f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]); 
        }
    }
    int res=0;
    for (int i=1;i<=n;i++) res=max(res,f[i][n+i]);
    cout << res;
    return 0;
}