Codeforces 1146G Zoning Restrictions dp

Zoning Restrictions

发现从左往右dp没有办法dp， 可以想到最大值的性质， 我们考虑构建笛卡尔树的过程。

如果 i 的l, r 的最大值， 那么经过 i 点的线段可以全部在枚举 i 的时候处理掉。

dp[ i ][ j ][ k ] 表示只关注i - j之间的点和线段所能得到的最大值， 转移方程就很容易写出来啦。

好像还能用网络流写， 然而并不会。。

#include<bits/stdc++.h>

using namespace std;

const int N = 50 + 7;

int n, h, m;
int val[N][N][N][N];
int dp[N][N][N];

int dfs(int l, int r, int up) {
    if(up < 0 || l > r) return 0;
    int &ans = dp[l][r][up];
    if(~ans) return ans;
    ans = dfs(l, r, up - 1);
    for(int j = l; j <= r; j++) {
        int tmp = val[l][r][j][up - 1] + up * up;
        tmp += dfs(l, j - 1, up);
        tmp += dfs(j + 1, r, up);
        ans = max(ans, tmp);
    }
    return ans;
}

int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d%d%d", &n, &h, &m);
    for(int i = 1; i <= m; i++) {
        int l, r, x, c;
        scanf("%d%d%d%d", &l, &r, &x, &c);
        for(int i = 1; i <= l; i++) {
            for(int j = r; j <= n; j++) {
                for(int k = l; k <= r; k++) {
                    val[i][j][k][x] -= c;
                }
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            for(int k = i; k <= j; k++) {
                for(int z = 1; z <= h; z++) {
                    val[i][j][k][z] += val[i][j][k][z - 1];
                }
            }
        }
    }

    printf("%d\n", dfs(1, n, h));

    return 0;
}

/*
*/