HDU-4540

2018-03-05

题目链接

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

题目大意

很简单的DP，代价是一维坐标之差，从第一行走到最后一行问代价最小是多少。
记录dp[i][j]是从第一行到第i行第j个位置的消耗。
状态转移方程为从dp[i][j]=min{dp[i-1][kk]+abs(j,k位置的坐标之差)},1<=kk<=K

代码

HDU-4540

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define INF 1<<31-1
int N,K;
int mmap[25][15],dp[25][15];
int main()
{
    while (~scanf("%d%d",&N,&K))
    {
        int ans=INF;
        for (int i=1;i<=N;i++)
            for (int j=1;j<=K;j++)
                scanf("%d",&mmap[i][j]);
        for (int i=1;i<=N;i++)
            for (int j=1;j<=K;j++)
                if (i == 1) dp[i][j]=0;
                else
                    dp[i][j]=INF;
        for (int i=2;i<=N;i++)
            for (int j=1;j<=K;j++)
            {
                for (int k=1;k<=K;k++)
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+abs(mmap[i][j]-mmap[i-1][k]));
            }
        for (int i=1;i<=K;i++)
            if (ans > dp[N][i]) ans=dp[N][i];
        printf("%d\n",ans);
    }
    return 0;
}

后记

今天只做了这一道题，是最简单的DP，很裸，还是中文的题干，正好现在也很晚了，也没想到能一次A。应该说有一点进步。今天发生了很多事，不过还蛮好的。
加油！
祝所有人平安吧。