<四边形不等式优化>[NOI1995]石子合并

留个坑

挺套路的

明天来写个总结

#include<cstdio>

#include<algorithm>

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

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

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

    return x * f;

}

const int maxn = 2007;

int dp[maxn][maxn],s[maxn][maxn],cnt[maxn];

int sum[maxn];

int dpm[maxn][maxn];

int main () {

    int n = read();

    for(int i = 1;i <= n;++ i) cnt[n + i] = cnt[i] = read(),sum[i] = sum[i - 1] + cnt[i];

    for(int i = n + 1;i <= n * 2;++ i) sum[i] = sum[i - 1] + cnt[i];

    for(int i = 1;i <= 2 * n;++ i) s[i][i] = i;

    for(int i = n * 2 - 1;i >= 1;-- i) {

        for(int j = i + 1;j <= n * 2;++ j) {

            int tmp = 0x7fffffff,loc = 0;

            dpm[i][j] = std::max(dpm[i][j - 1],dpm[i + 1][j]) + sum[j] - sum[i - 1];

            for(int k = s[i][j - 1];k <= s[i + 1][j];++ k) {

                if(tmp >dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]) {

                    tmp = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];

                    loc = k;

                }

            }

            dp[i][j] = tmp;

            s[i][j] = loc;

        }

    }

    int ansm = 0x7fffffff,ansx = 0;

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

        ansm = std::min(dp[i][i + n - 1],ansm) ;

        ansx = std::max(dpm[i][i + n - 1],ansx) ;

    }

    printf("%d\n%d",ansm,ansx);

    return 0;

}

巴特西

<四边形不等式优化>[NOI1995]石子合并

留个坑

最新文章

热门文章