信仰DP吧!

懵逼的 题目

改造前: 传送至 Codevs
改造后: 传送至 Vijos
传纸条: 传送至 Luogu

扯淡的 题解

先写改造前的就是4维dp嘛….这么小的范围不是想怎么写怎么写….
改造后的无非就是把一维压掉…可以通过记录走的总步数和向右/下的步数解决…
传纸条就是把两条路径一条强制在左一条在右(因为不能重复取)…

沙茶的 代码

改造前

//http://codevs.cn/problem/1043/
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define MAXN (10 + 5)
using namespace std;
int n;
int a[MAXN][MAXN];
int f[MAXN][MAXN][MAXN][MAXN];
void dp();
int tmax(int, int, int, int);
int main()
{
    scanf("%d", &n);
    memset(a, 0, sizeof(a));
    int srx, sry, srz;
    do
    {
        scanf("%d%d%d", &srx, &sry, &srz);
        if (!srx && !sry && !srz)
        {
            break;
        }
        a[srx][sry] = srz;
    }
    while(true);
    dp();
    printf("%d", f[n][n][n][n]);
    return 0;
}
void dp()
{
    memset(f, 0,sizeof(f));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                for (int kk = 1; kk <= n; kk++)
                {
                    f[i][j][k][kk] = tmax(f[i][j - 1][k][kk - 1], f[i][j - 1][k - 1][kk], f[i - 1][j][k][kk - 1], f[i - 1][j][k - 1][kk]) + ((i == k && j == kk) ? (a[i][j]) : (a[i][j] + a[k][kk]));
                    //printf("%d %d    %d %d: %d\n",i, j, k, kk, f[i][j][k][kk]);
                }
            }
        }
    }
}
int tmax(int x, int y, int xx, int yy)
{
    x = max(x, y);
    xx = max(xx, yy);
    return max(x, xx);
}

改造后

//https://vijos.org/p/1143
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (20 + 5)
const int zx[8][4] = {{-1, -1, -1, -1}, {-1, 0, -1, -1}, {-1, 0, 0, -1}, {-1, 0, 0, 0}, {-1, 0, -1, 0}, {-1, -1, 0, -1}, {-1, -1, -1, 0}, {-1, -1, 0, 0}};
using namespace std;
int n;
int ans;
int f[MAXN + MAXN][MAXN][MAXN][MAXN];// j, k, kk 表示横着走的步数 
int a[MAXN][MAXN];
int tmax(int, int, int, int);
void dp();
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    }
    dp();
    printf("%d", ans);
    return 0;
}
void dp()
{
    int maxstep = n << 1;
    for (int i = 1; i < maxstep; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                for (int kk = 1; kk <= n; kk++)
                {
                    f[i][j][k][kk] = tmax(i, j, k, kk);
                }
            }
        }
    }
    ans = f[maxstep - 1][n][n][n];
}
int tmax(int step, int h1, int h2, int h3)
{
    int maxp = 0;
    for (int i = 0; i < 8; i++)
    {
        maxp = max(maxp, f[step + zx[i][0]][h1 + zx[i][1]][h2 + zx[i][2]][h3 + zx[i][3]]);
    }
    if (h1 == h2 && h1 == h3)
    {
        return maxp + a[h1][step - h1 + 1];
    }
    if (h1 == h2)
    {
        return maxp + a[h1][step - h1 + 1] + a[h3][step - h3 + 1];
    }
    if (h2 == h3)
    {
        return maxp + a[h1][step - h1 + 1] + a[h3][step - h3 + 1];
    }
    if (h1 == h3)
    {
        return maxp + a[h1][step - h1 + 1] + a[h2][step - h2 + 1];
    }
    if (h1 != h2 && h1 != h3 && h3 != h2)
    {
        return maxp + a[h1][step - h1 + 1] + a[h2][step - h2 + 1] + a[h3][step - h3 + 1];
    }
}

传纸条

https://www.luogu.org/problem/show?pid=1006#sub
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int n;
int m;
int a[MAXN][MAXN];
int f[MAXN][MAXN][MAXN];// f[i][j][k] means it has used i steps && down j or k steps 
inline int tmax(int, int, int, int);
int main()
{
    memset(f, 0, sizeof(f));
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= m + n - 3; i++)
    {
        for (int j = 0; j < min(n, i + 1); j++)
        {
            for (int k = j + 1; k < min(n, i + 1); k++)
            {
                if ((i - k) >= m || (i - j) >= m)
                    continue;
                f[i][j][k] = max(f[i][j][k], f[i - 1][j][k] + a[i - j][j] + a[i - k][k]);
                if (j > 0)
                {
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k] + a[i - j][j] + a[i - k][k]);
                }
                if (k > 0)
                {
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1] + a[i - j][j] + a[i - k][k]);
                }
                if (k > 0 && j > 0)
                {
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 1] + a[i - j][j] + a[i - k][k]);
                }
//                printf("{i = %d; j = %d; k = %d}: %d\n", i, j, k, f[i][j][k]);
//                f[i][j][k] = tmax(f[i - 1][j][k], f[i - 1][j][k - 1], f[i - 1][j - 1][k - 1], f[i - 1][j - 1][k - 1]) + a[j][i - j] + a[k][i - k];
            }
        }
    }
    printf("%d", f[n + m - 3][n - 2][n - 1]);
    return 0;
}
inline int tmax(int a, int b, int c, int d)
{
    a = max(a, b);
    c = max(c, d);
    return max(a, b);
}

By 啥都不会的 Cansult