hdu Dragon Ball(dp)

http://acm.hdu.edu.cn/showproblem.php?pid=4362

题意：有m个阶段，每个阶段都有n个龙珠，当在某一阶段选择一个龙珠，该阶段其他龙珠都会消失。给出两个m*n的矩阵，第一个矩阵表示消灭第i个阶段第j个龙珠的位置，第二个矩阵表示取第i个阶段第j个龙珠消耗的能量，同时当第x个位置到第个位置需要消耗 | y - x|的能量。问最后每个阶段取走一个龙珠最小的能量消耗。

思路：状态转移方程很容易，dp[i][j] = min(dp[i-1][k] + abs( pos[i-1][k] - pos[i][j] ) ) + energy[i][j]。

但由于n较大，想着会TLE。试着敲出来，果真ＴＬＥ。改了改细节，然后加了个内联函数水过。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;

const int INF = 0x3f3f3f3f;

int n,m,x;
int pos[55][1010],ener[55][1010],dp[55][1010];

inline int chk(int x)
{
    if(x < 0)
        return -x;
    return x;
}

int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d %d %d",&n,&m,&x);
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
                scanf("%d",&pos[i][j]);
        }

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
                scanf("%d",&ener[i][j]);
        }

        for(int j = 0; j < m; j++)
            dp[0][j] = chk(pos[0][j]-x) + ener[0][j];

        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                int tmp = INF;
                for(int k = 0; k < m; k++)
                {
                    int sum = dp[i-1][k] + chk(pos[i-1][k] - pos[i][j]);
                    if(tmp > sum)
                        tmp = sum;

                }

                dp[i][j] = tmp+ener[i][j];
            }
        }

        int ans = INF;
        for(int j = 0; j < m; j++)
            ans = min(ans, dp[n-1][j]);
        printf("%d\n",ans);
    }
    
    return 0;
}

hdu Dragon Ball(dp),布布扣,bubuko.com

hdu Dragon Ball(dp)

原文：http://blog.csdn.net/u013081425/article/details/20958055