hdoj 4540: 웨 이 웨 이 고양이 시리즈 이야기 - 두더지 (dp 기초 문제 - 수 탑 사상)

목차
윌 리 엄 고양이 시리즈 - 두더지
 문제 풀이 방향:
ac 코드:
윌 리 엄 고양이 시리즈 - 두더지
Time Limit: 300/100 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 4422    Accepted Submission(s): 2128Problem Description
     
 두더지 놀이:
가설: 1. 매 순간 에 우 리 는 두더지 한 마 리 를 때 릴 수 있 고 그 후에 이 시간 에 나타 난 모든 두더지 가 바로 사라 집 니 다.2. 쥐 가 나타 난 위 치 는 일 직선 에 있 습 니 다. 만약 에 지난 시간 에 우리 가 x1 위치 에서 쥐 를 잡 았 다 면 다음 시간 에 우 리 는 x2 위치 에서 쥐 를 잡 았 습 니 다. 그러면 이때 우리 가 소모 하 는 에 너 지 는 abs (x1 - x2) 입 니 다.3. 첫 번 째 두더지 를 잡 으 면 에너지 소모 가 없습니다.지금 우 리 는 매 순간 땅 에서 튀 어 나 온 두더지 의 위 치 를 알 고 있 습 니 다. 매 순간 두더지 한 마 리 를 잡 으 려 면 최소한 얼마나 많은 에 너 지 를 소모 해 야 하 는 지 계산 하 세 요.
 Input
입력 데 이 터 는 여러 그룹의 테스트 용례 를 포함 합 니 다.각 그룹의 데이터 의 첫 줄 은 2 개의 정수 N 과 K (1 & lt; N & gt; = 20, 1 & gt; = K & gt; = 10) 로 N 시간 이 있 고 매 시간 K 마리 의 두더지 가 땅 에서 튀 어 나 온 다 는 뜻 이 며, 다음 N 줄 은 각 줄 마다 K 마리 의 두더지 가 나타 난 좌표 (좌 표 는 모두 정수 이 고 & lt; = 500) 를 나타 낸다.
Output
최소 소모 되 는 에 너 지 를 계산 하고 출력 하 십시오. 각 그룹의 데 이 터 는 한 줄 씩 출력 합 니 다.
 Sample Input

2 2 
1 10
4 9 
3 5 
1 2 3 4 5 
2 4 6 8 10 
3 6 9 12 15

Sample Output
1
1
 문제 풀이 방향:
첫 줄 의 dp 값 을 0 으로 초기 화하 고 각 줄 과 각 줄 의 각 요 소 를 순서대로 옮 겨 다 니 며 이 요 소 를 기준 으로 현재 줄 의 이전 줄 의 a [i] [j] (이전 줄 의 dp [i] [j] 알 고 있 음) 를 옮 겨 다 니 며 최소 누적 cost 를 찾 습 니 다.
상태 이동 방정식:

dp[i][j]=min(dp[i][j],dp[i-1][t]+abs(a[i][j]-a[i-1][t]))

i: 1 ~ n - 1 줄
j: 0 ~ k - 1 줄 내 원소
t: 이전 줄 에서 0 ~ k - 1 줄 내 요소
ac 코드:

#include 
#include 
#include 
#include 
#define maxn 100
using namespace std;
int a[maxn],dp[maxn];
int main()
{
    int n,k,i,j,t;//n   ，k   
    int dp[maxn][maxn],a[maxn][maxn];
    while(scanf("%d",&n)!=EOF)
    {
        int ans=INT_MAX;
        scanf("%d",&k);
        for(i=0;i