2018 March 08

区间dp

所谓区间dp，指在一段区间上进行动态规划，一般做法是由长度较小的区间往长度较大的区间进行递推，最终得到整个区间的答案，而边界就是长度为1以及2的区间。

转移方程

区间dp常见的转移方程如下：

dp(i,j) = min{dp(i,k-1) + dp(k,j)} + w(i,j)   (i < k <= j)

其中dp(i,j)表示在区间[i,j]上的最优值，w(i,j)表示在转移时需要额外付出的代价，min也可以是max。

四边形不等式

按上述转移方程递推的时间复杂度为O(n^3)，如果w函数满足区间单调性和四边形不等式，可通过四边形不等式将时间优化到O(n^2)。

当w满足以上两点时，dp也满足四边形不等式，定义s(i,j)表示dp(i,j)取得最优值时对应的下标，那么有s(i,j)单调，即s(i,j)<=s(i,j+1)<=s(i+1,j)。

将该单调性应用到转移方程中，可大大缩小k的枚举范围。

dp(i,j) = min{dp(i,k-1) + dp(k,j)} + w(i,j)    (s(i,j-1) <= k <= s(i+1,j))

51nod1021 石子归并

题面：N(<=100)堆石子摆成一条线，要将石子合并，每次只能选相邻的两堆合并成新的一堆，并将新堆的石子数记为该次操作的代价，求将所有堆合并为一堆的最小代价。

#include <bits/stdc++.h>
using namespace std;
int n, a[105], p[105], dp[105][105];
int sum(int l, int r) {
    return p[r] - p[l-1];
}
void go() {
    for (int i = 1; i <= n; i++)
        dp[i][i] = 0;
    for (int l = 2; l <= n; l++)
    for (int i = 1; i <= n; i++) {
        int j = i+l-1;
        if (j > n) break;
        dp[i][j] = INT_MAX;
        for (int k = i; k < j; k++)
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum(i,j));
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = a[i] + p[i-1];
    }
    go();
    cout << dp[1][n] << endl;
    return 0;
}

51nod1022 石子归并V2

题面：与上一题类似，但石堆改成了环状，且N<=1000。

分析：将石堆复制一份到原石堆后面，把环状问题转化为线状，然后用四边形不等式降低时间复杂度。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 2000;
LL n, N, a[maxn+5], p[maxn+5], dp[maxn+5][maxn+5], ss[maxn+5][maxn+5];
LL sum(LL l, LL r) {
    return p[r] - p[l-1];
}
void go() {
    for (LL i = 1; i <= N; i++) {
        dp[i][i] = 0;
        ss[i][i] = i;
    }
    for (LL l = 2; l <= n; l++)
    for (LL i = 1; i <= N; i++) {
        LL j = i+l-1;
        if (j > N) break;
        dp[i][j] = LLONG_MAX;
        for (LL k = ss[i][j-1]; k <= ss[i+1][j]; k++) {
            LL t = dp[i][k] + dp[k+1][j] + sum(i,j);
            if (dp[i][j] > t) {
                dp[i][j] = t;
                ss[i][j] = k;
            }
        }
    }
}
int main() {
    cin >> n;
    for (LL i = 1; i <= n; i++) {
        cin >> a[i];
        a[i+n] = a[i];
    }
    N = 2*n;
    for (LL i = 1; i <= N; i++)
        p[i] = a[i] + p[i-1];
    go();
    LL ans = LLONG_MAX;
    for (LL i = 1; i <= n; i++)
        ans = min(ans, dp[i][i+n-1]);
    cout << ans << endl;
    return 0;
}

uva1626 Brackets sequence

题面：给出一串由"(",")","[","]"组成的字符串，要求往其中添加最少的括号，使得整个串为合法括号序列，并打印任意一组可行解。

分析：记dp[i][j]表示区间[i,j]需添加的最少括号数，递推时需要注意类似"[][]"的情形。

#include <bits/stdc++.h>
using namespace std;
string s;
int T, dp[105][105];
int match(int x, int y) {
    return (s[x] == '(' && s[y] == ')')
        || (s[x] == '[' && s[y] == ']');
}
void DP(int len) {
    for (int i = 0; i < len; i++)
        dp[i][i] = 1;
    for (int i = 0; i+1 < len; i++)
        dp[i][i+1] = match(i,i+1) ? 0 : 2;
    for (int l = 2; l < len; l++)
    for (int i = 0; i < len; i++) {
        int j = i+l;
        if (j >= len) break;
        if (match(i,j))
            dp[i][j] = dp[i+1][j-1];
        else
            dp[i][j] = j-i+1;
        for (int k = i; k < j; k++)
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
    }
}
void print(int x, int y) {
    if (x > y) return;
    if (x == y) {
        if (s[x] == '(' || s[x] == ')')
            printf("()");
        else
            printf("[]");
        return;
    }
    if (match(x,y) && dp[x][y] == dp[x+1][y-1]) {
        printf("%c", s[x]); print(x+1, y-1); printf("%c", s[y]);
        return;
    }
    for (int k = x; k < y; k++) {
        if (dp[x][y] == dp[x][k] + dp[k+1][y]) {
            print(x, k); print(k+1, y);
            return;
        }
    }
}
int main() {
    cin >> T; getline(cin, s);
    for (int kase = 1; kase <= T; kase++) {
        getline(cin, s); getline(cin, s);
        if (kase > 1) cout << endl;
        if (s.length() == 0) {
            cout << "";
        } else {
            DP(s.length());
            print(0, s.length() - 1);
        }
        cout << endl;
    }
    return 0;
}

hdu4632 Palindrome subsequence

题面：给定字符串s，问它包含多少个回文子序列？输出结果对10007取余即可。

分析：记dp[i][j]表示区间[i,j]的答案，根据容斥原理进行递推即可。

#include <bits/stdc++.h>
using namespace std;
string s;
int T, dp[1005][1005], mod = 10007;
void DP(int len) {
    for (int i = 0; i < len; i++)
        dp[i][i] = 1;
    for (int i = 0; i+1 < len; i++)
        dp[i][i+1] = s[i] == s[i+1] ? 3 : 2;
    for (int l = 2; l < len; l++)
    for (int i = 0; i < len; i++) {
        int j = i+l;
        if (j >= len) break;
        dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
        if (s[i] == s[j])
            dp[i][j] += dp[i+1][j-1] + 1;
        dp[i][j] = (dp[i][j] % mod + mod) % mod;
    }
}
int main() {
    scanf("%d", &T);
    for (int kase = 1; kase <= T; kase++) {
        cin >> s;
        DP(s.length());
        cout << "Case " << kase << ": " << dp[0][s.length()-1] << endl;
    }
    return 0;
}
Table of Contents