hihocoder [Offer收割]编程练习赛18 C 最美和弦（dp）

题目链接：http://hihocoder.com/problemset/problem/1532

题解：一道基础的dp，设dp[i][j][k][l]表示处理到第几个数，当前是哪个和弦错了几次初始x值是多少。这里还要再辅助一个val[k]表示处理到当前情况只错了k次的最小值是多少因为改变的不止是和弦还有初始值，可以看一下代码理解一下。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#define inf 0X3f3f3f3f

using namespace std;

int a[][] , ans[][][] , dp[][][][] , val[];

int getnum(int i , int num , int ext) {

    int ans = ;

    ans = abs(a[i][] - num) + abs(a[i][] - num -  - ext) + abs(a[i][] - num - );

    return ans;

}

int main() {

    int n , k;

    scanf("%d%d" , &n , &k);

    for(int i =  ; i < n ; i++) {

        for(int j =  ; j <  ; j++) scanf("%d" , &a[i][j]);

    }

    for(int j =  ; j < n ; j++) {

        for(int i = - ; i <=  ; i++) {

            for(int l =  ; l <= k ; l++) {

                dp[j][][l][i + ] = dp[max(j -  , )][][l][i + ] + getnum(j , i , );

                if(l) dp[j][][l][i + ] = min(val[l - ] + getnum(j , i , ) , dp[j][][l][i + ]);

                dp[j][][l][i + ] = dp[max(j -  , )][][l][i + ] + getnum(j , i , );

                if(l) dp[j][][l][i + ] = min(val[l - ] + getnum(j , i , ) , dp[j][][l][i + ]);

            }

        }

        memset(val , inf , sizeof(val));

        for(int i = - ; i <=  ; i++) {

            for(int l =  ; l <= k ; l++) {

                val[l] = min(val[l] , dp[j][][l][i + ]);

                val[l] = min(val[l] , dp[j][][l][i + ]);

            }

        }

    }

    printf("%d\n" , val[k]);

    return ;

}