https://ac.nowcoder.com/acm/contest/1041/D
这题的关键在于对于第i步来说，一定是有一个点在p[i]的，所以这一维可以优化掉
而对于优化掉一维的这种DP来说，由i推向i+1更加简单，由i-1转移到i不好转移。。。。
#include<bits/stdc++.h> #define maxl 1010 using namespace std; int L,n,ans; int a[maxl],p[maxl]; int c[210][210]; int f[maxl][210][210]; inline void prework() { scanf("%d%d",&L,&n); for(int i=1;i<=L;i++) for(int j=1;j<=L;j++) scanf("%d",&c[i][j]); for(int i=1;i<=n;i++) scanf("%d",&p[i]); } inline void upd(int &x,int y) { if(y<x) x=y; } inline void mainwork() { for(int t=0;t<=n;t++) for(int i=1;i<=L;i++) for(int j=1;j<=L;j++) f[t][i][j]=2e9; f[0][1][2]=0;p[0]=3; for(int i=0;i<=n-1;i++) for(int x=1;x<=L;x++) for(int y=1;y<=L;y++) if(x!=y && x!=p[i] && y!=p[i]) { if(x!=p[i+1] && y!=p[i+1]) upd(f[i+1][x][y],f[i][x][y]+c[p[i]][p[i+1]]); if(p[i]!=p[i+1] && y!=p[i+1]) upd(f[i+1][p[i]][y],f[i][x][y]+c[x][p[i+1]]); if(p[i]!=p[i+1] && x!=p[i+1]) upd(f[i+1][x][p[i]],f[i][x][y]+c[y][p[i+1]]); } ans=2e9; for(int x=1;x<=L;x++) for(int y=1;y<=L;y++) ans=min(ans,f[n][x][y]); } inline void print() { printf("%d",ans); } int main() { prework(); mainwork(); print(); return 0; }
