「BZOJ-3997」「TJOI2015」-组合数学

给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。

题解

刚看完题以为是一道上下界网络流，但是一看范围就不对…

以下来自PoPoQQQ。

正解应根据 $Dilworth$ 定理有：

$DAG$ 的最小链覆盖 $=$ 最大点独立集

最小链覆盖指选出最少的链(可以重复)使得每个点都在至少一条链中，最大点独立集指最大的集合使集合中任意两点不可达，此题中最大点独立集显然是一个集合满足集合中任意两点都是左下-右上的关系。

dp一遍就能出解，时间复杂度 $O(Tmn)$

代码

/*
 * created by xehoth on 19-02-2017
 */
#include <bits/stdc++.h>

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    if (s == t) {
        t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
        if (s == t) return -1;
    }
    return *s++;
}

template<class T>
inline void read(T &x) {
    static bool iosig;
    static char c;
    for (iosig = false, c = read(); !isdigit(c); c = read()) {
        if (c == '-') iosig = true;
        if (c == -1) return;
    }
    for (x = 0; isdigit(c); c = read())
        x = (x + (x << 2) << 1) + (c ^ '0');
    if (iosig) x = -x;
}

template<class T1, class T2>
inline void read(T1 &a, T2 &b) {
    read(a), read(b);
}


template<class T1, class T2, class T3>
inline void read(T1 &a, T2 &b, T3 &c) {
    read(a), read(b), read(c);
}

template<class T1, class T2, class T3, class T4>
inline void read(T1 &a, T2 &b, T3 &c, T4 &d) {
    read(a), read(b), read(c), read(d);
}

const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;

inline void writeChar(char c) {
    if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
    *oh++ = c;
}

template<class T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        writeChar(48);
    } else {
        if (x < 0) writeChar('-'), x = -x;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
        while (cnt) writeChar(buf[cnt--]);
    }
}

inline void flush() {
    fwrite(obuf, 1, oh - obuf, stdout);
}

#define long long long

int main() {
    register int t, n, m;
    read(t);
    static int map[1002][1002];
    static long f[1002][1002];

    while (t--) {
        read(m, n);
        register long ans = 0;
        for (register int i = 1; i <= m; i++)
            for (register int j = 1; j <= n; j++)
                read(map[i][j]);

        memset(f, 0, sizeof(f));
        for (register int j = 1; j <= n; j++) {
            for (register int i = m; i; i--)
                f[i][j] = std::max(f[i][j - 1], f[i + 1][j - 1] + map[i][j]);
            for (register int i = m; i; i--)
                f[i][j] = std::max(f[i][j], f[i + 1][j]);
            ans = std::max(ans, f[1][j]);
        }
        print(ans), writeChar('\n');
    }
    flush();
    return 0;
}