学步园

参考http://hi.baidu.com/%8E%E1%D0%B3/blog/item/7506cd89ddf3791fc9fc7a6f.html

题目大意：有3辆车，开始都在点1上，要用这些车把杂志运送到各个城市里，当一个车在转移时，其他两辆车静止，并且两辆车不能跑到同一个位置，分配还得遵循递增的顺序，即城市i有了杂志后，车才能开到i+1城市送杂志。要求所有城市都送到杂志，汽车做过的路程和花费最小

解题思路：动态规划

dp[i][j][k]分别表示3辆车所在城市i,j,k时所花费的最小时间

因为城市要安装i,i+1的顺序送

可以反过来求，dp[i][j][k+1]表示dp[i][j][k]状态，k位置的车开到了k+1位置。

dp[i][j][k] = min(dp[i][j][k+1] + dist[k][k+1], dp[j][k][k+1] + dist[i][k+1], dp[i][k][k+1] + dist[j][k+1]);     1<=i,j <=k

当i=j != k时表示两辆车在运送，当i!=j!=k时表示三辆车在运送，i=j=k时表示1辆车在运送

之前，也在想这个划分状态，，，但是想着3辆车无序，然后车还分分别用1,2,3辆车完成任务，没继续想下去。。。。。

后面想的是分好几种情况来划分

第一种情况1~~~i城市交个一辆车去送杂志，i+1~~j城市给一辆车去送杂志，j+1~n城市交给一辆车去送杂志

第二种情况i~j交给一辆车去完成任务，i1<i<j <j1，i1~j1去除i~j城市交给一辆车去完成任务，然后同理,i2~j2去除城市i~j,i1~j1交给一辆车去完成任务

第三种，把城市划分为两部分，左边一部分城市交给两辆车去完成，右边一部分交给一辆车去完成

第四中，和第三种对应~~

这情况太复杂，后面都没法写了，，，，思路错了。。。想了老半天。。。状态没划分对。。。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 35;

int t, n, dist[maxn][maxn], dp[maxn][maxn][maxn];
int main()
{
       scanf("%d", &t);
    while(t-- != 0)
    {
        memset(dist, 0, sizeof(dist));
        memset(dp, 0, sizeof(dp));
        scanf("%d", &n);
        for(int i = 0; i < n - 1; i++)
        {
            for(int j = i + 1; j <= n - 1; j++)
                scanf("%d", &dist[i][j]);
        }
        for(int k = n - 2; k >= 0; k--)
        {
            for(int i = 0; i <= k; i++)
            {
                for(int j = 0; j <= k; j++)
                    dp[i][j][k] = min(dp[i][j][k+1] + dist[k][k+1], min(dp[j][k][k+1] + dist[i][k+1], dp[i][k][k+1] + dist[j][k+1]));
            }
        }
        printf("%d\n", dp[0][0][0]);
    }
   
    return 0;
}