题意:要求用三辆车往n座城市投递货物,起点都在一号城市,每辆车可以载任意数量的货物,投递顺序必须与城市编号递增序一致,并且,每次同时都只能有一辆车在跑路。求最短总路径之和。
思路:每时每刻,能够充分决定三辆车状态的变量即为三辆车的所在城市,因此,可以以三辆车所在城市为变量确立状态,可建立如下状态转移方程:
dp[i][j][k]=min(dp[i][j][k],dp[i+1][j][k]+g[i][i+1],dp[i+1][i][k]+g[j][i+1],dp[i+1][i][j]+g[k][i+1]);
对于该方程
1.首先,i表示此时状态所到达的最大城市编号,j,k为其余两车所在城市
2.采用倒序状态转移,即由dp[n][j][k]逐步转移到dp[1][1][1]
3.三辆车完全相同,因此不需要考虑其顺序,某一时刻三辆车所处城市编号从大到小依次是i,j,k时,下一步可能是j->i+1,i->i+1,k->i+1.
代码如下:
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int t, n; int g[40][40], dp[35][35][35]; int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); memset(dp, 0x3f, sizeof(dp)); for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { scanf("%d", &g[i][j]); g[j][i] = g[i][j]; } } /*for (int j = 1; j <= n; j++) for (int i = 1; i <= n; i++) for (int k = 1; k <= n; k++) g[i][k] = min(g[i][j] + g[j][k], g[i][k]);*/ for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dp[n][i][j] = 0; for (int i = n - 1; i >= 1; i--) { for (int j = 1; j == 1 || j < i; j++) { for (int k = 1; k == 1 || k < j; k++) { dp[i][j][k] = min(dp[i][j][k], dp[i + 1][j][k] + g[i][i + 1]); dp[i][j][k] = min(dp[i][j][k], dp[i + 1][i][k] + g[j][i + 1]); dp[i][j][k] = min(dp[i][j][k], dp[i + 1][i][j] + g[k][i + 1]); } } } int ans = 0x3f3f3f3f; for (int i = 1; i < n; i++) for (int j = 1; j < n; j++) ans = min(ans, dp[1][1][1]); printf("%d\n", dp[1][1][1]); } return 0; }