Magazine Delivery(POJ1695)【DP】

题意：要求用三辆车往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[][], dp[][][];

int main()

{

    scanf("%d", &t);

    while (t--)

    {

        scanf("%d", &n);

        memset(dp, 0x3f, sizeof(dp));

        for (int i = ; i < n; i++)

        {

            for (int j = i + ; 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 = ; i <= n; i++)

            for (int j = ; j <= n; j++)

                dp[n][i][j] = ;

        for (int i = n - ; i >= ; i--)

        {

            for (int j = ; j ==  || j < i; j++)

            {

                for (int k = ; k ==  || k < j; k++)

                {

                    dp[i][j][k] = min(dp[i][j][k], dp[i + ][j][k] + g[i][i + ]);

                    dp[i][j][k] = min(dp[i][j][k], dp[i + ][i][k] + g[j][i + ]);

                    dp[i][j][k] = min(dp[i][j][k], dp[i + ][i][j] + g[k][i + ]);

                }

            }

        }

        int ans = 0x3f3f3f3f;

        for (int i = ; i < n; i++)

            for (int j = ; j < n; j++)

                ans = min(ans, dp[][][]);

        printf("%d\n", dp[][][]);

    }

    return ;

}

By xxmlala

巴特西

Magazine Delivery(POJ1695)【DP】

最新文章

热门文章