Description

Solution

暴力DP很好想，\(f[i][j][k][l]\)表示处理到第\(i\)个任务，三个人在\(i,j,k\)的方案数。显然一个人应该在这个任务的地方，我们就省去那一维，注意要保证钦定办这个任务的人那一维一定被省略。

Code

#include <algorithm>

#include <cstdio>

#include <cstring>

const int N = 210;

const int INF = 0x3f3f3f3f;

int G[N][N];

int f[2][N][N], n, P[1010];

inline void upd(int &x, const int &y) {

    if (y < x) x = y;

}

int main() {

    n = read();

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

        for (int j = 1; j <= n; ++j) G[i][j] = read();

    memset(f, 0x3f, sizeof f);

    f[0][2][3] = 0;

    P[0] = 1;

    int nw = 0, pw = 1, x, m = 0;

    while (scanf("%d", &x) != EOF) {

        std::swap(nw, pw);

        P[++m] = x;

        memset(f[nw], 0x3f, sizeof f[nw]);

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

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

                upd(f[nw][j][k], f[pw][j][k] + G[P[m - 1]][x]);

                upd(f[nw][k][P[m - 1]], f[pw][j][k] + G[j][x]);

                upd(f[nw][j][P[m - 1]], f[pw][j][k] + G[k][x]);

            }

        }

    }

    int ans = 0x3f3f3f3f;

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

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

            upd(ans, f[nw][i][j]);

        }

    }

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

    return 0;

}

巴特西

[JSOI2010]快递服务

Description

Solution

Code

最新文章

热门文章