ZOJ 1428 Magazine Delivery

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1428

题意：有三辆车负责投递杂志，有N个位置L1, L2……LN，给出车从Li移动到Lj所用的时间D[i][j]，求出投递完所有的位置所用的最少时间。

开始时三辆车都在L1，投递时只能有一辆车移动，另外两个呆在原地。并且投递完位置Li-1才能投递Li。

思路：DP

递推公式：

D[i][j][k][m] = min(D[i - 1][x][k][m], D[i - 1][j][x][m], D[i - 1][j][k][x]) + time[x][i]; ( 1≤x＜i )

I代表到位置i所用的最少时间，j, k, m分别代表第一辆车，第二辆车，第三辆车的位置。

初始条件d[1][1][1][1] = 0；

去掉两种不可达的点：车的位置大于i，以及没有一辆车的位置等于i。因为到达位置i之后必须是有一辆车的位置在i上。

因为最前面那辆车的位置就是i，所以可以去掉一种状态。

D[i][j][k] = min(D[i][j][k], D[i - 1][j][k] + time[i - 1][i]); //移动第一辆车

D[i][i - 1][k] = min(D[i][i - 1][k], D[i - 1][j][k] + time[j][i]); //移动第二辆车

D[i][i - 1][j] = min(D[i][i - 1][j], D[i - 1][j][k] + time[k][i]); //移动第三辆车

i为最前面那辆车的位置，j为次前面，k为最后。

四状态的：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 
 5 const int MAXN = 30 + 5;
 6 const int INF = 1 << 30;
 7 
 8 int n;
 9 int time[MAXN][MAXN];
10 int dp[MAXN][MAXN][MAXN][MAXN];
11 
12 int min( int a, int b )
13 {
14     return a < b ? a : b;
15 }
16 
17 int DP( int i, int j, int k, int m )
18 {
19     if ( i == 0 ) return 0;
20     if ( dp[i][j][k][m] != -1 ) return dp[i][j][k][m];
21     if ( j != i && k != i && m != i ) return dp[i][j][k][m] = INF;       //该点不可达
22     if ( j > i || k > i || m > i ) return dp[i][j][k][m] = INF;          //该点不可达
23 
24     int MIN = INF;
25 
26     for ( int x = 1; x < i; x++ )
27     {
28         int temp1 = DP( i - 1, x, k, m );
29         if ( temp1 < INF )
30             MIN = min( MIN, temp1 + time[i][x] );
31 
32         int temp2 = DP( i - 1, j, x, m );
33         if ( temp2 < INF )
34             MIN = min( MIN, temp2 + time[i][x] );
35 
36         int temp3 = DP( i - 1, j, k, x );
37         if ( temp3 < INF )
38             MIN = min( MIN, temp3 + time[i][x] );
39     }
40 
41     return dp[i][j][k][m] = MIN;
42 }
43 
44 int main()
45 {
46     int T;
47     scanf( "%d", &T );
48     while ( T-- )
49     {
50         scanf( "%d", &n );
51 
52         for ( int i = 1; i < n; i++ )
53             for ( int j = i + 1; j <= n; j++ )
54             {
55                 scanf( "%d", &time[i][j] );
56                 time[j][i] = time[i][j];
57             }
58 
59         memset( dp, -1, sizeof(dp) );
60         dp[1][1][1][1] = 0;
61 
62         int MIN = INF;
63 
64         for ( int x = 1; x < n; x++ )
65             for ( int y = 1; y < n; y++ )
66             {
67                 MIN = min( MIN, DP( n, n, x, y ) );
68                 MIN = min( MIN, DP( n, x, n, y ) );
69                 MIN = min( MIN, DP( n, x, y, n ) );
70             }
71 
72         printf( "%d\n", MIN );
73     }
74 
75     return 0;
76 }

三状态的：

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int MAXN = 35;
 5 
 6 int time[MAXN][MAXN];
 7 int dp[MAXN][MAXN][MAXN];
 8 
 9 int min( int a, int b )
10 {
11     return a < b ? a : b;
12 }
13 
14 int main()
15 {
16     int T;
17     scanf( "%d", &T );
18     while ( T-- )
19     {
20         int n;
21         scanf( "%d", &n );
22 
23         memset( time, 0, sizeof(time) );
24         memset( dp, 0x7f, sizeof(dp) );
25 
26         for ( int i = 1; i < n; i++ )
27           for ( int j = i + 1; j <= n; j++ )
28           {
29               scanf( "%d", &time[i][j] );
30               time[j][i] = time[i][j];
31           }
32 
33         dp[1][1][1] = 0;
34         for ( int i = 2; i <= n; i++ )
35           for ( int j = 1; j < i; j++ )
36              for ( int k = 1; k < i; k++ )
37              {
38                  dp[i][j][k] = min( dp[i][j][k], dp[i - 1][j][k] + time[i - 1][i] );
39                  dp[i][i - 1][k] = min( dp[i][i - 1][k], dp[i - 1][j][k] + time[j][i] );
40                  dp[i][i - 1][j] = min( dp[i][i - 1][j], dp[i - 1][j][k] + time[k][i] );
41              }
42 
43         int MIN = 0x7fffffff;
44         for ( int i = 1; i < n; i++ )
45           for ( int j = 1; j < n; j++ )
46               MIN = min( MIN, dp[n][i][j] );
47 
48         printf( "%d\n", MIN );
49     }
50     return 0;
51 }