hdu 4540 打地鼠

中文题，题意非常简单，这里不赘述了。

显然状态之间具有联系，考虑使用动归。

设dp[i][j]表示第i时刻敲第j个出来的地鼠的最小消耗能量。

则构建dp方程如下：

dp[i][j]=min(dp[i][j],dp[i-1][p=1...k]+abs(pos[i][j]-pos[i-1][p]));

代码如下：

#include <cstdio>
#include <iostream>
#include <cmath> 
using namespace std;

int n,k;
int pos[25][15];
int dp[25][15];

void DP()
{
	for(int i=1;i<=k;i++)
		dp[1][i]=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			for(int p=1;p<=k;p++)
				dp[i][j]=min(dp[i][j],dp[i-1][p]+abs(pos[i][j]-pos[i-1][p]));
		}
	}
}

int main()
{
	while(scanf("%d %d",&n,&k)!=EOF)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=k;j++)
			{
				scanf("%d",&pos[i][j]);
				dp[i][j]=99999;
			}	
		DP();
		int res=99999;
		for(int i=1;i<=k;i++)
		{
			//printf("dp[%d][%d]=%d\n",n,i,dp[n][i]);
			res=min(res,dp[n][i]);
		}
		printf("%d\n",res);
	}
	return 0;
}