区间dp–例题

以后做的题目就在这总结，，，

石子合并 洛谷P1880

题意：一些石子堆围一圈，相邻的两堆石子可以合并成一堆，两堆石子合并后，产生的分数为合并的一堆的石子的数目，求这些石子堆合并成一堆后产生分数的最大值和最小值。
石子堆数目n<=100.
分析：考虑到数据很小，O(n^3)以内的复杂度都可，采用O(n^3)的作法。首先石子是围成一圈的，把他分解成长度为2n的链。dp[i][j]表示从i到j内的石子合并成一堆后的最大值/最小值。
先考虑基本的线性dp，即每次新加入一堆石子a[i]，然后更新区间内最优解，要依次更新从1-i分别到i内的值。更新顺序是dp[i][i]-dp[1][i]，对于每次更新的一个区间dp[j][i]，还是要暴力匹配最优值。状态转移方程

dp1[j][i] = max(dp1[j][i],dp1[j][k]+dp1[k+1][i]+num[j][i])
dp2[j][i] = min(dp2[j][i],dp2[j][k]+dp2[k+1][i]+num[j][i])
j<=k<i

dp数组的初始值要根据需要而定，0还是INFINITY。
第一层循环从1-2n，表示每次新加入一堆石子i，第二次循环从i到1，第三层循环从k到i。

#include <bits/stdc++.h>
using namespace std;
const int m = 0x3f3f3f3f3f;
int n;
int a[205];
int dp[205][205],dp2[205][205];
int num[205][205];
int main(){
    int ans1 = 0,ans2 = m;
    cin >> n;
    for (int i=1;i<=n;i++){
        cin >> a[i];
        a[n+i] = a[i];
    }
    for (int i=1;i<=2*n;i++)    num[i][i] = a[i];
    for (int i=2*n;i>=1;i--)    for (int j=i-1;j>=1;j--)
        num[j][i] = num[j+1][i] + a[j];
    for (int i=1;i<=2*n;i++)    for (int j=1;j<=2*n;j++)    dp2[i][j] = m;
    for (int i=1;i<=2*n;i++)    dp2[i][i] = 0;
    for (int i=1;i<=2*n;i++){
        for (int j=i-1;j>=1;j--){
            for (int k=j;k<=i-1;k++){
                dp[j][i] = max(dp[j][i],dp[j][k]+dp[k+1][i]+num[j][i]);
                dp2[j][i] = min(dp2[j][i],dp2[j][k]+dp2[k+1][i]+num[j][i]);
            }
        }
    }
    for (int i=1;i<=n;i++)    ans1 = max(ans1,dp[i][i+n-1]);
    for (int i=1;i<=n;i++)    ans2 = min(ans2,dp2[i][i+n-1]);
    cout << ans2 << endl;
    cout << ans1 << endl;
    return 0;
}

[USACO16OPEN]248 G 洛谷P3146

题意：给定一列数，相邻两个相同的数可以合并成一个比原来大1的数。求最终能合并出来的最大数。(不要求最终一定要合并成1个数)
数据量n<=248
分析：数据量也很小，同上，n^3的区间dp作法。

dp[i][j] = max(dp[i][j],(dp[i][k]==dp[k+1][j]?dp[i][k]+1:0)) i<=k<j

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
int dp[250][250];
int a[250],n;
int main(){
    std::ios::sync_with_stdio(false);
    int ans = 0;
    cin >> n;
    for (int i=1;i<=n;i++)  cin >> a[i];
    for (int i=1;i<=n;i++)  dp[i][i] = a[i];
    for (int i=1;i<=n;i++){
        for (int j=i-1;j>=1;j--){
            for (int k=j;k<i;k++){
                dp[j][i] = max(dp[j][i],(dp[j][k]==dp[k+1][i]?dp[j][k]+1:0));
                ans = max(dp[j][i],ans);
            }
        }
    }
    cout << ans;
    return 0;
}

能量项链 P1063

题意：去看链接吧，，，
分析：区间dp，做了几道区间dp后，差不多发现套路都差不多。区别就是最里面的那层循环，因题而异。

#include <bits/stdc++.h>
using namespace std;
int n;
int a[205];
int dp[205][205];
int main(){
    int n,ans = 0;
    cin >> n;
    for (int i=1;i<=n;i++){
        cin >> a[i];
        a[i+n] = a[i];
    }
    a[2*n+1] = a[1];
    for (int i=1;i<2*n;i++){
        for (int j=i-1;j>=1;j--){
            for (int k=j;k<i;k++){
                dp[j][i] = max(dp[j][i],dp[j][k]+dp[k+1][i]+a[j]*a[k+1]*a[i+1]);
            }
        }
    }
    for (int i=1;i<=n;i++)  ans = max(ans,dp[i][i+n-1]);
    cout << ans;
    return 0;
}