动态规划优化(三)

这部分内容主要介绍了四边形不等式和数位dp

四边形不等式

一维线性dp的四边形不等式优化

Acwing304

const int maxn = 100000 + 5;
int N, L, P;

class Q {
public:
    int x, l, r;
};
Q q[maxn];

ld f[maxn];
ll S[maxn];

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

ld cal(int i, int j) {
    ld ans = 1;
    ld num = abs((ld)(S[i] - S[j] + i - j - 1 - L));
    _rep(k, 1, P) ans *= num;
    return ans + f[j];
}

int bsearch(int i, int ql, int qr) {
    int ans = 0;
    while (ql <= qr) {
        int mid = (ql + qr) >> 1;
        if(q[mid].l <= i && q[mid].r >= i) {
            ans = mid;
            break;
        }
        if(q[mid].l <= i) ql = mid + 1;
        else qr = mid - 1;
    }

    return q[ans].x;
}

int findpos(int i, int x, int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (cal(mid, i) > cal(mid, x)) l = mid + 1;
        else r = mid;
    }
    return l;
}

void insert(int i, int& ql, int& qr) {
    int pos = -1;
    while (ql <= qr) {
        int lt = q[qr].l, rt = q[qr].r, xt = q[qr].x;
        if(cal(lt, i) <= cal(lt, xt)) pos = q[qr--].l;
        else {
            if(cal(rt, i) < cal(rt, xt)) {
                pos = findpos(i, xt, q[qr].l, q[qr].r);
                q[qr].r = pos - 1;
            }
            break;
        }
    }

    if(pos != -1) {
        q[++qr].l = pos;
        q[qr].r = N;
        q[qr].x = i;
    }
}

void solve() {
    init();
    cin >> N >> L >> P;

    // == get poetry sentences ==
    _rep(i, 1, N) {
        char str[35];
        scanf("%s", str);
        S[i] = S[i - 1] + strlen(str);
    }
    // == poetry sentences finished ==

    // == monotonic dp ==
    int ql = 1, qr = 1;
    q[1].x = 0;
    q[1].l = 1;
    q[1].r = N;

    _rep(i, 1, N) {
        int j = bsearch(i, ql, qr);
        if(i == 1) assert(j == 0);
        f[i] = cal(i, j);

        // == then pop front and try to insert i ==
        while (ql <= qr && q[ql].r <= i) ql++;
        q[ql].l = i + 1;
        insert(i, ql, qr);
        // == monotonic queue finished ==
    }
    // == monotonic finished ==

    if(f[N] > 1e18) puts("Too hard to arrange");
    else cout << (ll)f[N] << endl;

    _rep(i, 1, 20) putchar('-');
    cout << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    cin >> T;
    while (T--) solve();
}

二维dp，四边形不等式，决策单调性

const int maxn = 5000 + 5;
const int inf = 0x3f3f3f3f;

int N;
int F[maxn][maxn], P[maxn][maxn];
int a[maxn];
int sum[maxn];

void init() {
    Set(F, inf);
    Set(P, 0);
    Set(sum, 0);

    _rep(i, 1, N) {
        F[i][i] = 0;
        P[i][i] = i;
    }
}

void dp() {
    init();
    _rep(i, 1, N) {
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }

    _forDown(i, N - 1, 1) _rep(j, i + 1, N) {
        _rep(k, P[i][j - 1], P[i + 1][j]) {
            int val = F[i][k] + F[k + 1][j] + (sum[j] - sum[i - 1]);
            if(val < F[i][j]) {
                F[i][j] = val;
                P[i][j] = k;
            }
        }
    }

    printf("%d\n", F[1][N]);
}

int main() {
    freopen("input.txt", "r", stdin);
    while (cin >> N && N) {
        dp();
    }
}

加西亚-瓦克斯算法

POJ1738

const int maxn = 50000 + 5;
int N, tot;
ll ans, a[maxn];

void init() {
    tot = 1;
    ans = 0;
}

void dfs(int k) {
    ll tmp = a[k] + a[k - 1];
    ans += tmp;
    tot--;

    // for successor, move right
    _for(i, k, tot) a[i] = a[i + 1];

    // for pre, while a[i - 1] < tmp, move left
    int i = 0;
    for(i = k - 1; i >= 1 && a[i - 1] < tmp; i--) a[i] = a[i - 1];

    a[i] = tmp;

    while (i >= 2 && a[i] >= a[i - 2]) {
        int r = tot - i;
        dfs(i - 1);
        i = tot - r;
    }

}

void GarsiaWachs() {
    _for(i, 0, N) scanf("%lld", &a[i]);
    _for(i, 1, N) {
        a[tot++] = a[i];
        while (tot >= 3 && a[tot - 1] >= a[tot - 3]) dfs(tot - 2);
    }
    while (tot > 1) dfs(tot - 1);
    printf("%lld\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    while (cin >> N && N) {
        init();
        GarsiaWachs();
    }
}

计数dp专题

逆元法求组合数

codeforces559C

const int SZ = 2000 + 10;
const int maxn = 200000 + 10;
const ll mod = 1000000000 + 7;
int h, w, n;

ll jc[maxn], jcinv[maxn];
int f[SZ];

struct A {
    int x, y;
    bool operator< (const A& rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
};
A a[SZ];

// == init jc ==
inline ll power(ll a, int b) {
    ll ans = 1;
    for(; b; b >>= 1) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}

void init() {
    Set(f, 0);
    jc[0] = 1;
    jcinv[0] = 1;

    _rep(i, 1, maxn) {
        jc[i] = jc[i - 1] * i % mod;
        jcinv[i] = power(jc[i], mod - 2);
    }
}
// == init finished ==

// == calculate C ==
int C(int n, int m) {
    return jc[n] * jcinv[m] % mod * jcinv[n - m] % mod;
}
// == calculate finished ==

// == input files ==
void inp() {
    cin >> h >> w >> n;
    _rep(i, 1, n) {
        scanf("%d%d", &a[i].x, &a[i].y);
    }
    sort(a + 1, a + 1 + n);
    a[n + 1].x = h, a[n + 1].y = w;
}
// == input finsihed ==

// == dp ==
void dp() {
    _rep(i, 1, n + 1) {
        f[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);
        //debug(f[i]);
        _for(j, 1, i) {
            if(a[j].x > a[i].x || a[j].y > a[i].y) continue;
            f[i] = (f[i] - (ll)f[j] * C(a[i].x - a[j].x + a[i].y - a[j].y, a[i].x - a[j].x)) % mod;
        }
    }
    cout << (f[n + 1] + mod) % mod << endl;
}
// == dp finished ==

int main() {
    freopen("input.txt", "r", stdin);

    init();
    //debug(jc[2000]);
    // debug(jcinv[2000]);
    inp();
    dp();
}