小菜吃鸡腿

小菜吃鸡腿

特别裸的区间 dp ，而且之前还写过一样的题，居然没写出来，55555，主要还是因为把区间 dp 的思路给忘了

区间 dp 的主要思路：假设有一段区间[l,r]，当l和r缩为最小的单位区间的时候肯定会有一个初始值，这个是无疑的，然后当[l,r]的区间长度扩大的时候，尝试去在区间内找一个k使得这整个区间[l,r]的值为最大（即满足题目要求）。

整理一下区间 dp 的几个步骤：

总共三个for

第一个 遍历区间长度len

第二个遍历起始位置即得出l和r的坐标，即可得到区间[l,r]

第三个遍历区间[l,r]的切分点k，从而找到最满足条件的dp[l][r]（最大值或最小值）

代码：

// Created by CAD on 2019/8/21.
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll dp[60][60];
int w[55];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;++i) cin>>w[i];
    for(int k=3;k<=n;++k)
        {
            for (int l=1; l+k-1<=n; ++l)
            {
                int r=l+k-1;
                for(int i=l+1;i<=r-1;++i)
                    dp[l][r]=max(dp[l][r],dp[l][i]+dp[i][r]+w[l]*w[r]);
            }
        }
    cout<<dp[1][n]<<endl;
    return 0;
}

递归版本：

// Created by CAD on 2019/8/21.
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll dp[60][60];
int w[55];
ll dfs(int l,int r)
{
    ll &ret=dp[l][r];
    if(l>r) return 0;
    if(ret) return ret;
    for(int k=l+1;k<=r-1;++k)
        ret=max(ret,dfs(l,k)+dfs(k,r)+w[l]*w[r]);
    return ret;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;++i) cin>>w[i];
    cout<<dfs(1,n)<<endl;
    return 0;
}

貌似感觉递归写起来更加方便些