題意簡述

有3部車在k個城市間旅游，每次只能移動一部車，去第k個城市的前提是前k-1個城市都去過。
求旅行完k個城市的最短距離

分析

將狀態表示出來，直接dp即可
記f[a,b,c]表示三部車分別在a,b,c城市的最短距離(a>b>c)
那么枚舉每個可行狀態，更新f[a+1,b,c],f[a+1,a,c],f[a+1,b,c]即可

代碼

#include<cstdio> #define fo(i,a,b) for(int i=a;i<=b;i++) int n,f[120][120][120],a[200][200],te,ans; // f[i][j][k] i>=j>=k int main(){ scanf("%d",&n); fo(i,1,n) a[i][i]=0x3fffffff; fo(i,1,n-1) fo(j,i+1,n){ scanf("%d",&a[i][j]); //a[j][i]=0x3fffffff; } fo(i,1,n) fo(j,1,n)//1..i fo(k,1,n)//1..j f[i][j][k]=0x3fffffff; f[1][1][1]=0; fo(i,1,n-1) fo(j,1,i) fo(k,1,j){ te=f[i][j][k]+a[i][i+1];// if (te<f[i+1][j][k]) f[i+1][j][k]=te; te=f[i][j][k]+a[j][i+1]; if (te<f[i+1][i][k]) f[i+1][i][k]=te; te=f[i][j][k]+a[k][i+1]; if (te<f[i+1][i][j]) f[i+1][i][j]=te; } ans=0x3fffffff; fo(i,1,n) fo(j,1,n) if (f[n][i][j]<ans) ans=f[n][i][j]; printf("%d\n",ans); return 0; }

總結

以上是生活随笔為你收集整理的VIJOS 1547 逆转，然后再见的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。