HDU 4540 威威猫系列故事——打地鼠（DP）

点我看题目

题意 ：中文题，不详述。

思路 ： 状态转移方程 dp[ i ][ j ] = dp[i-1][k] + fabs(a[ i ][ j ]-a[i-1][k]) ;

dp[i][j]代表的是在 i 时刻如果敲第j坐标上的地鼠需要的最小消耗。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
using namespace std ;
int a[30][30] ;
int dp[1000][510] ;
const int INF = 99999999 ;
int main()
{
    int N,K ;
    while(~scanf("%d %d",&N,&K))
    {
        for(int i = 0 ; i < N ; i++)
        for(int j = 0 ; j < K ; j++)
        scanf("%d",&a[i][j]) ;
        for(int i = 0 ; i < K ; i++)
        dp[0][i] = 0 ;
        for(int i = 1 ; i < N ; i++)
        for(int j = 0 ; j < K ; j++)
        dp[i][j] = INF ;
        for(int k = 0 ; k < N ; k++)
        {
            for(int i = 0 ; i < K ; i++)
            {
                for(int j = 0 ; j < K ; j++)
                {
                    if(dp[k][i] > dp[k-1][j] + fabs(a[k][i]-a[k-1][j]))
                    dp[k][i] = dp[k-1][j]+fabs(a[k][i]-a[k-1][j]) ;
                }
            }
        }
        int minn = INF ;
        for(int i = 0 ; i < K ; i++)
        if(dp[N-1][i] < minn)
         minn=  dp[N-1][i];
         printf("%d
",minn) ;
    }
    return 0 ;
}