bzoj 1820 dp

最普通dp要4维，因为肯定有一个在上一个的位置，所以可以变为3维，然后滚动数组优化一下。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

int n, m, cur, a[][], b[];

LL dp[][][];

int main() {

    scanf("%d", &n);

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

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

            scanf("%d", &a[i][j]);

    b[] = ;

    while(scanf("%d", &b[++m]) != EOF){}

    memset(dp[cur], INF, sizeof(dp[cur]));

    dp[cur][][] = dp[cur][][] = ;

    LL ans = INF;

    for(int i = ; i <= m; i++) {

        cur ^= ;

        memset(dp[cur], INF, sizeof(dp[cur]));

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

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

                dp[cur][j][k] = min(dp[cur][j][k], dp[cur^][j][k] + a[b[i-]][b[i]]);

                dp[cur][b[i-]][k] = min(dp[cur][b[i-]][k], dp[cur^][j][k] + a[j][b[i]]);

                dp[cur][j][b[i-]] = min(dp[cur][j][b[i-]], dp[cur^][j][k] + a[k][b[i]]);

            }

        }

    }

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

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

            ans = min(ans, dp[cur][i][j]);

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

    return ;

}

/*

*/

相关文章