dp动态规划(四)Ranges Style

区间dp，Ranges Style

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。

令状态f[i, j] 表示将下标位置i 到j 的所有元素合并能获得的价值的最大值，那么

f[i, j] = max{f(i, k) + f(k+1, j) + cost}

// 区间dp的几种模型特征
subsets 0110101
        0404500
consecutive ranges
        (ab)(cde)(fg)
nested ranges
        (((a)(bc))(def))(ghijkl)

Consecutive Ranges Style

例题，Pearls

#include <bits/stdc++.h>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int a[N], p[N], n, T;
int mem[N][N];
int best(int u, int last)
{
    if (u == n + 1) return 0;
    int &ret = mem[u][last];
    if (ret != INF) return ret;
    int sum = 10;
    for (int i = last; i <= u; i++) sum += a[i];
    //buy now, add to right now interval
    ret = min(ret, sum * p[u] + best(u + 1, u + 1));
    if (u != n) ret = min(ret, best(u + 1, last));
    return ret;
}
int main()
{
    cin >> T;
    while (T--){
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i] >> p[i];
        memset(mem, 0x3f, sizeof mem);
        printf("%d\n", best(1, 1));
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int a[N], p[N], n, T;
int mem[N][N];
int s[N];
int best(int u, int last)
{
    if (u == n + 1) return 0;
    int &ret = mem[u][last];
    if (ret != INF) return ret;
    int sum = 10 + s[u] - s[last - 1];
    //buy now, add to right now interval
    ret = min(ret, sum * p[u] + best(u + 1, u + 1));
    if (u != n) ret = min(ret, best(u + 1, last));
    return ret;
}
int main()
{
    cin >> T;
    while (T--){
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i] >> p[i];
        memset(s, 0, sizeof s);
        for (int i = 1; i <= n; i++) s[i] += s[i - 1] + a[i];
        memset(mem, 0x3f, sizeof mem);
        printf("%d\n", best(1, 1));
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int a[N], p[N], n, T, s[N];
int dp[N];
int main()
{
    cin >> T;
    while (T--){
        memset(s, 0, sizeof s);
        memset(dp, 0x3f, sizeof dp);
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i] >> p[i];
        for (int i = 1; i <= n; i++) s[i] += s[i - 1] + a[i];
        dp[0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++)
                dp[i] = min(dp[i], dp[j - 1] + (s[i] - s[j - 1] + 10) * p[i]);
        cout << dp[n] << '\n';
    }
    return 0;
}

Nested Ranges Style

例题，CasketOfStar

// my_code, cannot submit to Topcoder
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int weight[N], mem[N][N];
int n;
int best(int i, int j)
{
    if (j - i + 1 <= 2) return 0;
    if (j - i + 1 == 3) return weight[i] * weight[j];
    int &ret = mem[i][j];
    if (ret != -1) return ret;
    for (int k = i + 1; k < j; k++)
        ret = max(ret, best(i, k) + best(k, j) + weight[i] * weight[j]);
    return ret;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> weight[i];
    memset(mem, -1, sizeof mem);
    cout << best(1, n) << '\n';
    return 0;
}

例题，Cutting Sticks

//Cutting Sticks，请上机练习

例题，Optimal Array Multiplication Sequence

// 难度：提高+/省选-
// 需要递归输出方案
// 请上机操作

General Ranges Style

例题，String to Palindrome

// 递归写法，my 10739_1.cpp
# include<vector>
# include<string>
# include<iostream>
using namespace std;
string A, B;
const int MAX  = 1000+9;
int memo[MAX][MAX];
int best(int i, int j)
{
    if(i >= j)
        return 0;
    int &ret = memo[i][j];
    if(ret != -1)
        return ret;
    ret = best(i+1, j-1) + (A[i] != A[j]);
    ret = min(ret, best(i+1, j)+1);
    ret = min(ret, best(i, j-1)+1);
    return ret;
}
int main() {
    int num;
    cin >> num;
    for (int i = 1; i <= num; i++) {
        cin >> A;
        memset(memo, -1, sizeof memo);
        cout << "Case " << i << ": " << best(0, (int)A.size()-1) << endl;
    }
    return 0;
}

// 循环写法
#include<iostream>
#include<string>
using namespace std;
int min(int a, int b, int c)
{
    if(b < a)        a = b;
    if(c < a)        a = c;
    return a;
}
int A[1001][1001]; /* The cost of substring A[i][j] */
int main() 
{
    int i, j, k, len, cases, diag;
    string str;
    cin>>cases;
    for (k = 1; k <= cases; k++)
    {        
        cin>>str;
        for (i=0; i<str.size(); i++) /* Base case in diagonal */
            A[i][i] = 0; /* Empty string */
        for (len = 2; len <= str.size(); len++)    /* O(n^2) */
        {    /* when len = 2 --> Special case */
            for (i = 0; i+len<=str.size(); i++)
            {
                j = i + len - 1, diag = 0;
                if (str[i] != str[j])
                    diag = 1;
                if( i+1 <= j-1 ) /* at least j-i > 1 */
                    A[i][j] = min(A[i+1][j]+1, A[i][j-1]+1, A[i+1][j-1]+diag);
                else    /* Undefined Stage (Not in base case) i = j+1 */
                    A[i][j] = diag; /* j=i+1Tow char string */
            }
        }
        cout<<"Case "<<k<<": "<<A[0][str.size()-1]<< "\n";
    }
    return 0;
}
// by zqiceberg
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int T, idx;
int dp[N][N];
char s[N];
int main()
{
    cin >> T;
    while (T--){
        scanf("%s", s);
        int LEN = strlen(s);
        for (int i = 0; i < LEN; i++) dp[i][i] = 0;
        for (int len = 2; len <= LEN; len++)
            for (int i = 0; i + len <= LEN; i++){
                int j = i + len - 1;
                int flag = 0;
                if (s[i] != s[j]) flag = 1;
                if (i + 1 <= j - 1){
                    dp[i][j] = dp[i + 1][j - 1] + flag;
                    dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
                    dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
                }
                else dp[i][j] = flag;
            }
        printf("Case %d: %d\n", ++idx, dp[0][LEN - 1]);
    }
    return 0;
}

Tips: 对比一下线性dp的 最短编辑距离 edit distance

例题代码

// Cutting Sticks
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int a[N], l, n;
int mem[N][N];
int best(int i, int j)
{
    if (j - i <= 1) return 0;
    if (j - i == 2) return a[j] - a[i];
    int &ret = mem[i][j];
    if (ret != 0x3f3f3f3f) return ret;
    for (int k = i + 1; k < j; k++){
        ret = min(ret, best(i, k) + best(k, j) + a[j] - a[i]);
    }
    return ret;
}
int main()
{
    while (cin >> l){
        if (l == 0) break;
        cin >> n;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        a[0] = 0, a[n + 1] = l;
        memset(mem, 0x3f, sizeof mem);
        printf("The minimum cutting is %d.\n", best(0, n + 1));
    }
    return 0;
}

// Optimal Array Multiplication Sequence
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 20, INF = 0x3f3f3f3f;
PII a[N];
int path[N][N];
int n, idx; 
int mem[N][N];
void print(int i, int j)
{
    if (j == i){
        printf("A%d", i);
        return ;
    }
    if (j - i == 1){
        printf("(A%d x A%d)", i, j);
        return ;
    }
    int k = path[i][j];
    printf("(");
    print(i, k); 
    printf(" x ");
    print(k + 1, j);
    printf(")");
}
int best(int i, int j)
{
    if (j - i == 0) return 0;
    if (j - i == 1) return mem[i][j] = a[i].first * a[i].second * a[j].second;
    if (mem[i][j] != INF) return mem[i][j];
    int &ret = mem[i][j];
    for (int k = i; k < j; k++){
        int t = best(i, k) + best(k + 1, j) + a[i].first * a[k].second * a[j].second;
        if (t < ret){
            ret = t;
            path[i][j] = k;
        }
    }
    return ret;
}
int main()
{
    while (cin >> n && n){
        idx++;
        for (int i = 1; i <= n; i++){
            cin >> a[i].first >> a[i].second;
        }
        memset(mem, 0x3f, sizeof mem);
        best(1, n);
        printf("Case %d: ", idx);
        print(1, n);
        puts("");
    }
    return 0;
}