最近搞DP遇到几个优化上的问题…
优化大法好$n ^ 3$变$n ^ 2$

懵逼的 题目

  1. 传送至 Luogu
  2. 传送至 Codevs

扯淡的 题解

  1. 首先是先打一个n ^ 3暴力好了…结果WAWAWA…
    发现两边的k重叠了…就是说左区间和右区间都包含了k…GG
    然后终于把暴力改对了…愉快的改正解
    WAWAWA…
    怀疑人生
    把DP的优化全都搜了…感觉并不合适(因为加上还是WA)…
    然后看了看题解(我错了)…发现我一开始的优化思路是对的…WTF???
    但是没有考虑到最小值是有两种情况, 一个是从左边的最小, 一个是从右边的最小…
    终于A了…

  2. 看了看四边形不等式才做的…
    当前的最优转移点k一定在[le, ri - 1][le + 1][ri]两个子区间的最优转移之间, 并不会证明
    感觉四边形不等式用起来很简单啊(flag), 就是不会证啊
    然后WAWAWA…
    发现其实是可以取到s[le + 1][ri]的 (其实这种优化直接加<=就好了吧反正时间也超不了太多, 换来正确性和简单是值得的)…然后我写的是k < s[le + 1][ri]…GG
    改过来, A了

沙茶的 代码

  1. 记录区间的最值来优化(并不知道叫什么名字…)

AC代码


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define INF (10000000)
using namespace std;
int n;
int sum[MAXN][MAXN];
int ls[MAXN][MAXN];
int rs[MAXN][MAXN];
int a[MAXN];
int f[MAXN][MAXN];
int fr[MAXN];
void init();
void dp();
inline void getint(int*);
int main()
{
    int t;
    getint(&t);
    while (t--)
    {
        init();
        dp();
        printf("%d\n", f[1][n]);
    }
    return 0;
}
void init()
{
    getint(&n);
    for (register int i = 1; i <= n; i++)
    {
        getint(a + i);
        fr[i] = fr[i - 1] + a[i];
        f[i][i] = a[i];
        rs[i][i] = ls[i][i] = a[i];
    }

}
void dp()
{
    for (register int i = 1; i <= n; i++)
    {
        for (register int j = 1; j <= n - i + 1; j++)
        {
            int le = j;
            int ri = j + i;
            f[le][ri] = max(fr[ri] - fr[le - 1], max(fr[ri] - fr[le - 1] - ls[le][ri - 1], fr[ri] - fr[le - 1] - rs[le + 1][ri]));
            ls[le][ri] = min(ls[le][ri - 1], f[le][ri]);
            rs[le][ri] = min(rs[le + 1][ri], f[le][ri]);
        }
    }
}
inline void getint(int* re)
{
    *re = 0;
    char x = 0;
    int zf = 1;
    while (x < '0' || x > '9')
    {
        x = getchar();
        if (x == '-')
        {
            zf = -1;
        }
    }
    while (x >= '0' && x <= '9')
    {
        *re = ((*re) << 1) + ((*re) << 3) + x - '0';
        x = getchar();
    }
    (*re) *= zf;
}
/*
2
1 -1
2 1 2
*/

/*
1
5
-5 6 -3 2 -4
*/

/*
1
5
-1 -1 -1 -1 -1
*/

k重复: 爆零的暴力

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define INF (10000000)
using namespace std;
int n;
int sum[MAXN][MAXN];
int a[MAXN];
int f[MAXN][MAXN];
int fr[MAXN];
void init();
void dp();
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(fr, 0, sizeof(fr));
        memset(sum, 0, sizeof(sum));
        memset(f, 0, sizeof(f));
        memset(a, 0, sizeof(a));
        init();
        dp();
        printf("%d\n", f[1][n]);
    }
    return 0;
}
void init()
{
    scanf("%d", &n);
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            f[i][j] = -INF;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        fr[i] = fr[i - 1] + a[i];
        f[i][i] = a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            sum[j][i] = fr[i] - fr[j - 1];
        }
    }
}
void dp()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n - i + 1; j++)
        {
            int le = j;    
            int ri = j + i;
            f[le][ri] = sum[le][ri];
            for (int k = le + 1; k < ri; k++)
            {
                if (f[k][ri] != -INF && f[le][k] != -INF)
                f[le][ri] = max(f[le][ri], max(sum[le][ri] - f[k][ri], sum[le][ri] - f[le][k]));
            }
        }
    }
}
/*
2
1 -1
2 1 2
*/

/*
1
5
-5 6 -3 2 -4
*/

/*
1
5
-1 -1 -1 -1 -1
*/

暴力DP

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define INF (10000000)
using namespace std;
int n;
int sum[MAXN][MAXN];
int a[MAXN];
int f[MAXN][MAXN];
int fr[MAXN];
void init();
void dp();
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(fr, 0, sizeof(fr));
        memset(sum, 0, sizeof(sum));
        memset(f, 0, sizeof(f));
        memset(a, 0, sizeof(a));
        init();
        dp();
        printf("%d\n", f[1][n]);
    }
    return 0;
}
void init()
{
    scanf("%d", &n);
    for (int i = 0; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            f[i][j] = -INF;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        fr[i] = fr[i - 1] + a[i];
        f[i][i] = a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            sum[j][i] = fr[i] - fr[j - 1];
        }
    }
}
void dp()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n - i + 1; j++)
        {
            int le = j;
            int ri = j + i;
            f[le][ri] = sum[le][ri];
            for (int k = le; k < ri; k++)
            {
                f[le][ri] = max(f[le][ri], max(sum[le][ri] - f[k + 1][ri], sum[le][ri] - f[le][k]));
            }
        }
    }
}
/*
2
1 -1
2 1 2
*/

/*
1
5
-5 6 -3 2 -4
*/

/*
1
5
-1 -1 -1 -1 -1
*/

爆零优化: 只考虑了区间最值, 没有考虑是在左边还是右边

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define INF (10000000)
using namespace std;
int n;
int sum[MAXN][MAXN];
int a[MAXN];
int f[MAXN][MAXN];
int minf[MAXN][MAXN];
int fr[MAXN];
void init();
void dp();
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(fr, 0, sizeof(fr));
        memset(sum, 0, sizeof(sum));
        memset(f, 0, sizeof(f));
        memset(a, 0, sizeof(a));
        init();
        dp();
        printf("%d\n", f[1][n]);
    }
    return 0;
}
void init()
{
    scanf("%d", &n);
    for (int i = 0; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            f[i][j] = -INF;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        fr[i] = fr[i - 1] + a[i];
        minf[i][i] = f[i][i] = a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            sum[j][i] = fr[i] - fr[j - 1];
        }
    }
}
void dp()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n - i + 1; j++)
        {
            int le = j;
            int ri = j + i;
            minf[le][ri] = min(minf[le + 1][ri], minf[le][ri - 1]);
            f[le][ri] = max(sum[le][ri], max(sum[le][ri] - minf[le][ri], sum[le][ri] - minf[le][ri]));
            minf[le][ri] = min(minf[le][ri], f[le][ri]);
        }
    }
}
/*
2
1 -1
2 1 2
*/

/*
1
5
-5 6 -3 2 -4
*/

/*
1
5
-1 -1 -1 -1 -1
*/
  1. 四边形不等式
#include <cstdio>
#include <cstring>
#define MAXN (3000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF (0x7fffffff)

int n;
int a[MAXN];
int s[MAXN][MAXN];
int f[MAXN][MAXN];
int fr[MAXN];

int ans = INF;

void dp();
int main()
{
    memset(f, 0x7f, sizeof(f));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        fr[i] = a[i] + fr[i - 1];
        s[i][i] = i;
        f[i][i] = 0;
    }
    dp();
    printf("%d", f[1][n]);
    return 0;
}
void dp()
{
    int le;
    int ri;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; i + j <= n; j++)
        {
            le = j;
            ri = i + j;
            for (int k = s[le][ri - 1]; k <= s[le + 1][ri]; k++)
            {
                if (f[le][ri] > (f[le][k] + f[k + 1][ri] + fr[ri] - fr[le - 1]))
                {
                    f[le][ri] = f[le][k] + f[k + 1][ri] + fr[ri] - fr[le - 1];
                    s[le][ri] = k;
                }
            }
        }
    }
}

/*
4
4 5 9 4
*/

/*
4
4 1 1 4
*/

By Noip药丸的 Cansultc

Only my RAILGUN can shoot it.必ず

我永远爱御坂9982