KickStart 2020 Round D-B Alien Piano
题目 题解和总结:/blog/2020-07-15-ks-2020-d/
Code
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n = 0;
int v[1000006] = {};
int dp[1000006][4] = {};
int main() {
int T = 0;
scanf("%d", &T);
for (int t = 1; t <= T; ++t) {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", v + i);
}
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = dp[0][1] = dp[0][2] = dp[0][3] = 0;
for (int i = 1; i < n; ++i) {
for (int cur = 0; cur < 4; ++cur) {
for (int lst = 0; lst < 4; ++lst) {
int val = dp[i - 1][lst];
if ((cur > lst && v[i] <= v[i - 1])
|| (cur == lst && v[i] != v[i - 1])
|| (cur < lst && v[i] >= v[i - 1])) {
++val;
}
dp[i][cur] = min(dp[i][cur], val);
}
}
}
int ans = 0x3f3f3f3f;
for (int i = 0; i < 4; ++i) ans = min(ans, dp[n - 1][i]);
printf("Case #%d: %d\n", t, ans);
}
}
<EOF>