时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
某个夜晚，Bob将他弹奏的钢琴曲录下来发给Jack，Jack感动之余决定用吉他为他伴奏。
我们可以用一个整数表示一个音符的音高，并可认为Bob弹奏的曲子是由3N个整数构成的一个序列。其中每个整数的取值范围是[-200, 200]。
Jack共弹奏 N 个和弦，每个和弦由三个音符组成。Jack可以自行决定和弦的第一个音符，其后的两个音符由第一个音符与和弦种类所决定。Jack共弹奏两种和弦：大三和弦与小三和弦。假设Jack决定某个和弦的第一个音符是 x，那么对于大三和弦，余下两个音符依序是 x+4和 x+7；对于小三和弦，余下两个音符依序是x+3和x+7。两个和弦相同，当且仅当其对应位置的三个音符都相同。其中每个和弦的第一个音符x的取值范围也是[-200, 200]。
Jack很懒，一旦决定弹奏某个和弦后，便不愿意更换和弦。即如果他开始弹奏1,5,8这个和弦，他将不停重复1,5,8,1,5,8,1,5,8……Bob觉得这样过于单调，于是Jack妥协：他表示愿意更换和弦，但最多更换K次。最开始选择和弦不计在更换次数内。
我们用不和谐值衡量乐曲与伴奏之间的契合程度。记某时刻Bob弹奏音符的音高为a，Jack弹奏音符的音高为b，则该点的不和谐值为|a-b|。整首乐曲的不和谐值等于这3N个不和谐值之和。
Jack希望选取最美的一组和弦，使得整首乐曲的不和谐值达到最小。你需要输出这个最小值。
输入
第一行两个正整数 N (≤1000), K (≤20).
第二行3N个整数(取值范围[-200, 200])为Bob的曲谱。
输出
一个整数，为乐曲最小不和谐值。
样例输入
3 1
-1 3 6 4 7 11 21 26 28
样例输出
15
这题做很难受，最后看着题解才恍然大悟，总是有那么点感觉，但就是没法抓住那点灵感。还是DP的题目做的太少，思考不够深度。
Jack可以使用两种和弦，大三和小三，然后每种和弦都有400个起调（-200~200），最多可以变调K次，求Jack让伴奏和音乐最小的不和谐度是多少。
状态描述：
dp[i][j][t][x] 表示的是考虑第i个调调，已经变调j次，此时使用t和弦，起调为x的情况下整首歌曲的不和谐度的最小值
状态转移方程是
dp[i][j][t][x] = min{ dp[i-1][j][t][x] (不变调的情况下)， dp[i-1][j-1][0~1][0~400] } + cost(i, x, t)
cost(i, x, t)表示在第i个调调，使用t和弦，起调为x，所产生的不和谐度是多少。
其中有个别扭的地方就是，在变调的状态转移，有一个是t跟x都和当前考虑的状态一样，这样就是没有变调，但是却加在了状态转移里面。
其实是应该拿出来不考虑的，但是其实如果可以多变一次调，那么可以肯定的是，他的最小值一定不会比多变一次调的状态要大，所以dp[i-1][j][t][x] <= dp[i-1][j-1][t][x],所以加上并不会影响结果，还会让代码变复杂。
还有一点就是优化的一点就是使用g[i][j]来表示i层使用j次变调所能达到的最小值，可以降低两层循环，减少复杂度。
于是，状态转移方程dp[i][j][t][x] = min{ dp[i-1][j][t][x], g[i-1][j-1] } + cost(i, x, t)g[i][j] = min{ dp[i][j][0~1][0~400] }
代码：
#include <iostream> #include <string.h> #include <stdlib.h> #include <stdio.h> using namespace std; const int INF = 0x3f3f3f3f; typedef long long LL; const int N = 1000 + 5; const int X = 400 + 20; const int offs = 200; const int K = 20 + 5; int n, k; int a[N][3]; int dp[N][K][2][X]; // 1000 * 20 * 2 * 400 == 16000000 int g[N][X]; //dp[i][j][t][x] = min(dp[i-1][j][t][x], dp[i-1][j-1][t(0~1)][x(-200 ~ 200 )]) + cost(i,x,t); // t 0 small 1 large int cost(int i, int x, int t) { int ans = 0; if(t) ans = abs(a[i][0] - x) + abs(a[i][1] - x - 4) + abs(a[i][2] - x - 7); else ans = abs(a[i][0] - x) + abs(a[i][1] - x - 3) + abs(a[i][2] - x - 7); return ans; } int main() { scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) { for(int j = 0; j < 3; j++) scanf("%d", &a[i][j]); } memset(dp, 0, sizeof(dp)); memset(g, 0x3f, sizeof(g)); for(int i = 1; i <= n; i++) { for(int x = 0; x <= 400; x++) { for(int j = 0; j <= k; j++) { dp[i][j][1][x] = dp[i-1][j][1][x] + cost(i, x - 200, 1); if(j) dp[i][j][1][x] = min(dp[i][j][1][x], g[i-1][j-1] + cost(i, x - 200, 1)); dp[i][j][0][x] = dp[i-1][j][0][x] + cost(i, x - 200, 0); if(j) dp[i][j][0][x] = min(dp[i][j][0][x], g[i-1][j-1] + cost(i, x - 200, 0)); } } for(int x = 0; x <= 400; x++) { for(int j = 0; j <= k; j++) { g[i][j] = min(g[i][j], dp[i][j][0][x]); g[i][j] = min(g[i][j], dp[i][j][1][x]); } } } int ans = INF; for(int j = 0; j <= k; j++) ans = min(ans, g[n][j]); printf("%d ", ans); return 0; }