BZOJ 3997: [TJOI2015]组合数学 [偏序关系 DP]

时间：2023-12-19 12:58:44

3997: [TJOI2015]组合数学

题意：\(n*m:\ n \le 1000\)网格图，每个格子有权值。每次从左上角出发，只能向下或右走。经过一个格子权值-1.至少从左上角出发几次所有权值为0。

容易发现偏序关系

\[x_1 \le x_2, y_1 \le y_2
\]

最少链数=最长反链大小

但是本题每个元素有权值

容易发现，最少链数=最大权值反链的权值

然后我沙茶的写了一个\(O(n^4)\)的DP就T掉了

怒写二维树状数组，A了

其他人怎么辣么快啊，然后发现直接

f[i][j] = max(f[i+1][j-1] + a[i][j], max(f[i][j-1], f[i+1][j]))

这样DP就行了...

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=1005;

inline int read() {

    char c=getchar(); int x=0, f=1;

    while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

    while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

    return x*f;

}

int n, m, a[N][N];

namespace bit {

    ll c[N][N];

    inline void add(int x, int y, ll d) { //printf("-----------d %lld\n",d);

        for(int i=x; i; i-=i&-i)

            for(int j=y; j<=m; j+=j&-j) c[i][j] = max(c[i][j], d);

    }

    inline ll cal(int x, int y) {

        if(x<1 || x>n || y<1 || y>m) return 0;

        ll ans = 0;

        for(int i=x; i<=n; i+=i&-i)

            for(int j=y; j; j-=j&-j) ans = max(ans, c[i][j]);// printf("c %d %d  %lld  ans %lld\n", i, j, c[i][j], max(ans, c[i][j]));

        return ans;

    }

}

int main() {

    //freopen("in", "r", stdin);

    int T=read();

    while(T--) {

        n=read(); m=read();

        for(int i=1; i<=n; i++)

            for(int j=1; j<=m; j++) a[i][j] = read(), bit::c[i][j] = 0;

        ll ans=0;

        for(int i=n; i>=1; i--)

            for(int j=1; j<=m; j++) {

                ll now = bit::cal(i+1, j-1) + a[i][j];

                bit::add(i, j, now);

                ans = max(ans, now);

            }

        printf("%lld\n", ans);

    }

}

相关文章