动态规划专题(五)

本节内容主要讲述动态规划中
环形与后效性处理常见的策略

环形与后效性处理

const int maxn = 4000;
const int inf = 0x3f3f3f3f;
int N, B;
int U[maxn];

int f[2][maxn][2];

void init() {
    Set(f, -inf);
}

void initdp1() {
    f[1 & 1][1][1] = f[1 & 1][0][0] = 0;
}

void initdp2() {
    f[1 & 1][1][1] = U[1];
}

int dp1() {
    _rep(i, 2, N) _rep(j, 0, B) {
        f[i & 1][j][0] = max(f[(i - 1) & 1][j][0], f[(i - 1) & 1][j][1]);
        if(j - 1 >= 0) f[i & 1][j][1] = max(f[(i - 1) & 1][j - 1][0], f[(i - 1) & 1][j - 1][1] + U[i]);
    }
    return max(f[N & 1][B][0], f[N & 1][B][1]);
}

int dp2() {
    _rep(i, 2, N) _rep(j, 0, B) {
            f[i & 1][j][0] = max(f[(i - 1) & 1][j][0], f[(i - 1) & 1][j][1]);
            if(j - 1 >= 0) f[i & 1][j][1] = max(f[(i - 1) & 1][j - 1][0], f[(i - 1) & 1][j - 1][1] + U[i]);
    }

    return f[N & 1][B][1];
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &N, &B);

    _rep(i, 1, N) scanf("%d", &U[i]);
    if(B == 0) {
        printf("0");
        return 0;
    }

    init();
    initdp1();
    int ans1 = dp1();

    init();
    initdp2();
    int ans2 = dp2();

    printf("%d", max(ans1, ans2));
}

复习：滑动窗口最值问题

CH5501
CH5501

const int maxn = 2000000 + 5;
int A[maxn], ans = 0;
int N;

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    _rep(i, 1, N) scanf("%d", &A[i]);
    _rep(i, N + 1, (N << 1)) A[i] = A[i - N];

    deque<int> dq;
    dq.push_front(1);
    _rep(i, 2, (N << 1)) {
        while (!dq.empty() && dq.back() < i - N / 2) dq.pop_back();
        ans = max(ans, A[i] + A[dq.back()] + i - dq.back());
        while (!dq.empty() && A[i] - i >= A[dq.front()] - dq.front()) dq.pop_front();
        dq.push_front(i);
    }
    printf("%d\n", ans);
}

行阶梯形矩阵处理后效性问题

codeforces24D


const int maxn = 1000 + 5;
double f[maxn][maxn], D[maxn][maxn];
int N, M;
int x, y;

void init() {
    Set(f, 0);
    Set(D, 0);
}

void dp() {
    _forDown(i, N - 1, x) {
        D[1][1] = D[M][M] = 2.0 / 3.0;
        D[1][M + 1] = f[i + 1][1] / 3.0 + 1;

        D[1][2] = D[M][M - 1] = -1 / 3.0;
        D[M][M + 1] = f[i + 1][M] / 3.0 + 1;

        _rep(j, 2, M - 1) {
            D[j][j - 1] = D[j][j + 1] = -1 / 4.0;
            D[j][j] = 3.0 / 4.0;
            D[j][M + 1] = f[i + 1][j] / 4.0 + 1;
        }
        // row of matrix finished
        _rep(j, 1, M) {
            double r = D[j + 1][j] / D[j][j];

            D[j + 1][j] = 0;
            D[j + 1][j + 1] -= r * D[j][j + 1];
            D[j + 1][M + 1] -= r * D[j][M + 1];
        }
        _forDown(j, M, 1) {
            double r = D[j - 1][j] / D[j][j];

            D[j - 1][j] = 0;
            D[j - 1][M + 1] -= r * D[j][M + 1];

            f[i][j] = D[j][M + 1] / D[j][j];
        }
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &N, &M);
    scanf("%d%d", &x, &y);
    init();

    if(M == 1) {
        printf("%d\n", (N - x) * 2);
        return 0;
    }
    dp();
    printf("%.4lf\n", f[x][y]);
}

线性dp总结

POJ1952

NOIP2010


const int maxn = 120 + 5;
const int maxA = 350 + 5;
const int maxm = 40 + 5;
int N, M;
int A[maxA];
int C[maxn];

int f[maxn][maxm][maxm][maxm];

void initdp() {
    Set(f, 0);
}

void dp() {
    _rep(i, 1, M) for(int l1 = 0; l1 <= C[1] && l1 <= M; l1++)
        for(int l2 = 0; l2 <= C[2] && l2 <= M - l1; l2++)
            for(int l3 = 0; l3 <= C[3] && l3 <= M - l1 - l2; l3++) {
                int& ans = f[i][l1][l2][l3];
                int l4 = i - l1 - l2 - l3;
                int u = 1 + l1 + 2 * l2 + 3 * l3 + 4 * l4;

                if(l4) ans = f[i - 1][l1][l2][l3];
                if(l1) ans = max(ans, f[i - 1][l1 - 1][l2][l3]);
                if(l2) ans = max(ans, f[i - 1][l1][l2 - 1][l3]);
                if(l3) ans = max(ans, f[i - 1][l1][l2][l3 - 1]);

                ans += A[u];
            }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &N, &M);

    _rep(i, 1, N) scanf("%d", &A[i]);
    _rep(i, 1, M) {
        int x;
        scanf("%d", &x);
        C[x]++;
    }

    // input finished, then dp
    initdp();
    dp();
    printf("%d\n", f[M][C[1]][C[2]][C[3]] + A[1]);
}

SGU104


const int maxn = 100 + 10;
int f[maxn][maxn];
const int inf = 0x3f3f3f3f;

int A[maxn][maxn], N, M;
int pre[maxn][maxn];

void initdp() {
    Set(f, -inf);
    Set(pre, 0);
    _for(i, 0, maxn) f[0][i] = 0;
}

int dp() {
    _rep(i, 1, N) _rep(j, i, M - (N - i)) {
            int& ans = f[i][j];
            _for(k, i - 1, j) {
                int tmp = f[i - 1][k] + A[i][j];
                if(tmp > ans) {
                    ans = tmp;
                    pre[i][j] = k;
                }
            }
        }

    int ans = -inf;
    _rep(i, 1, M) ans = max(ans, f[N][i]);
    return ans;
}


void print(int i, int j) {
    if(i == 0) return;
    print(i - 1, pre[i][j]);
    printf("%d ", j);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &N, &M);

    _rep(i, 1, N) _rep(j, 1, M) scanf("%d", &A[i][j]);

    // then dp()
    initdp();
    int res = dp();
    printf("%d\n", res);
    int j;
    _rep(i, 1, M) if(f[N][i] == res) j = i;

    print(N, j);
}

POJ1952


const int maxn = 5000 + 5;
const int inf = 0x3f3f3f3f;
int f[maxn];
int g[maxn];
int A[maxn];
int N;

void initdp() {
    Set(f, 0);
    Set(g, 0);
    A[0] = inf;
    g[0] = 1;
}

int dp() {
    _rep(i, 1, N) {
        _forDown(j, i - 1, 0) {
            if(A[j] > A[i]) f[i] = max(f[i], f[j] + 1);
        }
    }

    int ans = 0;
    _rep(i, 1, N) ans = max(ans, f[i]);
    return ans;
}

void dp2() {
    _rep(i, 1, N) {
        _for(j, 1, i) if(A[i] == A[j]) f[j] = -inf;

        _for(j, 0, i) if( (j == 0 || A[j] > A[i]) && f[i] == f[j] + 1) g[i] += g[j];
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    _rep(i, 1, N) scanf("%d", &A[i]);

    initdp();
    int res = dp();
    printf("%d ", res);

    dp2();
    int cnt = 0;
    _rep(i, 1, N) if(f[i] == res) cnt += g[i];
    printf("%d\n", cnt);
}

LCS执行方案输出

POJ1934
POJ1934


const int maxn = 80 + 5;
char A[maxn], B[maxn];
int N = 0, M = 0;
const int inf = 0x3f3f3f3f;

int f[maxn][maxn];
int locA[maxn][26], locB[maxn][26];
vector<string> res;



void initdp() {
    Set(f, 0);
    Set(locA, 0);
    Set(locB, 0);
    assert(N != 0);
    res.clear();

    _rep(i, 1, N) {
        _for(ch, 0, 26) {
            if(A[i] - 'a' == ch) locA[i][ch] = i;
            else locA[i][ch] = locA[i - 1][ch];
        }
    }

    _rep(i, 1, M) {
        _for(ch, 0, 26) {
            if(B[i] - 'a' == ch) locB[i][ch] = i;
            else locB[i][ch] = locB[i - 1][ch];
        }
    }
}

int dp() {
    _rep(i, 1, N) _rep(j, 1, M) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(A[i] == B[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    return f[N][M];
}

void dfs(int x, int y, int len, string str) {
    if(len == 0) {
        res.push_back(str);
        return;
    }
    if(!x || !y) return;

    _for(ch, 0, 26) {
        int l1 = locA[x][ch], l2 = locB[y][ch];
        if(f[l1][l2] != len) continue;

        dfs(l1 - 1, l2 - 1, len - 1, char(ch + 'a') + str);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%s", A + 1);
    scanf("%s", B + 1);
    N = strlen(A + 1), M = strlen(B + 1);
    //debug(N), debug(M);

    initdp();
    int len = dp();
    //debug(ans);
    string str;
    dfs(N, M, len, str);

    sort(res.begin(), res.end());
    _for(i, 0, res.size()) cout << res[i] << endl;
}

线性dp杂题

POJ1722

POJ1722


const int BASE = 10000;
const int maxn = 20000 + 5;
const int maxl = 100 + 5;
int N, T;
int f[maxl][maxn];
int A[maxn];
int op[maxl];

void initdp() {
    Set(f, 0);
    Set(op, 0);
}

void dp() {
    f[1][BASE + A[1]] = 1;
    f[2][BASE + A[1] - A[2]] = -1;
    _rep(i, 3, N) _rep(j, 0,  BASE + BASE) {
        if(f[i - 1][j]) {
            f[i][j + A[i]] = 1;
            f[i][j - A[i]] = -1;
        }
    }
}

void out(int T) {
    int S = T + BASE;
    _forDown(i, N, 2) {
        op[i] = f[i][S];
        if(op[i] == 1) S -= A[i];
        if(op[i] == -1) S += A[i];
    }

    int cnt = 0;
    _rep(i, 2, N) {
        if(op[i] == 1) {
            cout << i - 1 - cnt << endl;
            cnt++;
        }
    }

    _rep(i, 2, N) {
        if(op[i] == -1) cout << 1 << endl;
    }
}


int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &N, &T);
    _rep(i, 1,N) scanf("%d", &A[i]);

    initdp();
    dp();
    out(T);
}

POJ1187

POJ1187


const int maxd = 30 + 5;
const int maxn = 10 + 5;
const int mod = 11380;

int f[maxd][maxn][maxn][maxn];
int D, L1, L2, L3;

void initdp() {
    Set(f, 0);
    _rep(d, 0, D) f[d][0][0][0] = 1;
}

void dp() {
    _rep(d, 1, D) {
        _rep(l1, 0, L1) _rep(l2, 0, L2) _rep(l3, 0, L3) {
            if(!l1 && !l2 && !l3) continue;
            int sum = 0;
            _rep(p, 1, l1) _rep(q, 0, l2) _rep(r, 0, l3) sum = (sum + (f[d-1][p-1][q][r] * f[d][l1-p][l2-q][l3-r] % mod)) % mod;
            _rep(q, 1, l2) _rep(r, 0, l3) sum = (sum + (f[d-1][0][q-1][r] * f[d][l1][l2-q][l3-r]) % mod) % mod;
            _rep(r, 1, l3) sum = (sum + (f[d-1][0][0][r-1] * f[d][l1][l2][l3-r]) % mod) % mod;

            f[d][l1][l2][l3] = sum;
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d%d", &L1, &L2, &L3, &D);

    initdp();
    if(D == 0) {
        if(!L1 && !L2 && !L3) puts("1");
        else puts("0");

        return 0;
    }

    // then dp()
    dp();
    printf("%d\n", (f[D][L1][L2][L3] - f[D-1][L1][L2][L3] + mod) % mod);
}

区间dp

字符串折叠

POJ2176
POJ2176


const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
char str[maxn];
int N;

class Seg {
public:
    int plen;
    char pstr[maxn];
};

Seg f[maxn][maxn];

void init() {
    N = strlen(str + 1);
}

void initdp() {
    _rep(i, 1, N) {
        f[i][i].plen = 1;
        f[i][i].pstr[0] = str[i];
    }
}

void folding(int i, int j) {
    // fold str[i, j]
    int l = j - i + 1;
    _rep(ll, 1, l / 2) {
        if(l % ll) continue;

        int ii = i, jj = i + ll;
        while (str[ii] == str[jj] && jj <= j) ii++, jj++;

        if(jj > j) {
            // can fold
            // ll from [1, l / 2], try to find min fold
            // 2(A) is better than 1(AA)
            int cnt = l / ll;

            // str[i, i + ll - 1] is pattern substring
            sprintf(f[i][j].pstr, "%d", cnt);
            strcat(f[i][j].pstr, "(");
            strcat(f[i][j].pstr, f[i][i + ll - 1].pstr);
            strcat(f[i][j].pstr, ")");
            f[i][j].plen = strlen(f[i][j].pstr);

            break;
        }
    }
}

void dp() {
    _rep(len, 2, N) _rep(i, 1, N - len + 1) {
        int j = i + len - 1;
        f[i][j].plen = inf;

        folding(i, j);

        _for(k, i, j) {
            if(f[i][j].plen > f[i][k].plen + f[k + 1][j].plen) {
                f[i][j].plen = f[i][k].plen + f[k + 1][j].plen;
                strcpy(f[i][j].pstr, f[i][k].pstr);
                strcat(f[i][j].pstr, f[k + 1][j].pstr);
            }
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%s", str + 1) != EOF) {
        init();
        initdp();
        dp();

        printf("%s\n", f[1][N].pstr);
    }
}

多重背包

多重背包


const int maxn = 6 + 3;
const int maxm = 20000 + 5;
const int N = 6;

bitset<maxm> f;
int A[maxn];

void initdp() {
    f &= 1;
    f[0] = 1;
}

bool dp() {
    int totV = 0;
    _rep(x, 1, 6) totV += x * A[x];

    if(totV & 1) return false;
    else totV /= 2;

    _rep(i, 1, N) {
        // value is i
        for(int p = 1; p <= A[i]; p <<= 1) {
            f |= (f << (p * i));
            A[i] -= p;
        }
        if(A[i]) f |= (f << (A[i] * i));
    }

    if(f[totV]) return true;
    else return false;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (1) {
        int finished = true;
        _rep(i, 1, N) scanf("%d", &A[i]);

        _rep(i, 1, N) if(A[i] != 0) finished = false;
        if(finished) return 0;

        initdp();
        bool flag = dp();

        if(flag) puts("Can");
        else puts("Can't");
    }
}

2D区间dp

POJ1191
POJ1191


const int N = 8;
const int maxn = 15 + 2;

int f[maxn][N + 2][N + 2][N + 2][N + 2];
int A[N + 2][N + 2];
int n;
int S[N + 2][N + 2];
double tot = 0;
const int inf = 0x3f3f3f3f;

void init() {
    Set(f, inf);
    Set(S, 0);

    _rep(i, 1, N) _rep(j, 1, N) {
            S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j];
        }

    _rep(x1, 1, N) _rep(y1, 1, N) {
            _rep(x2, x1, N) _rep(y2, y1, N) {
                    int t = S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1];
                    f[0][x1][y1][x2][y2] = t * t;
                }
        }
}

void dp(int k, int x1, int y1, int x2, int y2) {
    int& ans = f[k][x1][y1][x2][y2];
    ans = inf;

    _for(a, x1, x2) {
        ans = min(ans, f[k-1][x1][y1][a][y2] + f[0][a+1][y1][x2][y2]);
        ans = min(ans, f[k-1][a+1][y1][x2][y2] + f[0][x1][y1][a][y2]);
    }

    _for(b, y1, y2) {
        ans = min(ans, f[k-1][x1][y1][x2][b] + f[0][x1][b+1][x2][y2]);
        ans = min(ans, f[k-1][x1][b+1][x2][y2] + f[0][x1][y1][x2][b]);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);

    _rep(i, 1, N) _rep(j, 1, N) {
            scanf("%d", &A[i][j]);
            tot += A[i][j];
        }

    init();
    _rep(k, 1, n - 1) _rep(x1, 1, N) _rep(y1, 1, N) {
                _rep(x2, x1, N) _rep(y2, y1, N) {
                        dp(k, x1, y1, x2, y2);
                    }
            }

    double avr = (double)(tot / n);
    //debug(tot);
    double ans = sqrt(1.0 * f[n - 1][1][1][N][N] / n - (avr * avr));
    printf("%.3f\n", ans);
}

区间dp破环成链

破环成链


const int maxn = 100 + 2;
int f[maxn * 2][maxn * 2];
int e[maxn * 2];
int N;

void initdp() {
    Set(f, 0);
}

void dp() {
    _rep(len, 1, N) for(int i = 1; i + len - 1 <= (N << 1); i++) {
        int j = i + len - 1;

        _for(k, i, j) {
            f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + e[i] * e[k + 1] * e[j + 1]);
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &N) != EOF) {
        _rep(i, 1, N) scanf("%d", &e[i]);
        _rep(i, N + 1, (N << 1)) e[i] = e[i - N];

        //_rep(i, 1, 2*N) printf("%d ", e[i]);

        initdp();
        dp();

        int ans = 0;
        _rep(i, 1, N) ans = max(ans, f[i][i + N - 1]);

        printf("%d\n", ans);
    }
}

区间dp增加状态

POJ1390
POJ1390


const int maxn = 200 + 10;
int f[maxn][maxn][maxn];
int A[maxn];
int N;

void init() {
    Set(f, -1);
}

int dp(int i, int j, int k) {
    if(i > j) return 0;
    int& ans = f[i][j][k];
    if(i == j) return ans = (1 + k) * (1 + k);
    if(ans >= 0) return ans;

    int p = j;
    while (p >= i && A[p] == A[j]) p--;
    p++;

    ans = dp(i, p-1, 0) + (k + j-p+1) * (k + j-p+1);
    _for(q, i, p) {
        if(A[q] == A[j] && A[q+1] != A[q]) {
            ans = max(ans, dp(i, q, k+j-p+1) + dp(q+1, p-1, 0));
        }
    }

    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    _rep(kase, 1, T) {
        printf("Case %d: ", kase);
        scanf("%d", &N);
        _rep(i, 1, N) scanf("%d", &A[i]);
        init();

        // then dp()
        printf("%d\n", dp(1, N, 0));
    }
}