[Blog] [Docs] [Code] [Slides] [About]

KickStart 2020 Round D-B Alien Piano

动态规划

2020-07-15 20:32 CST

题目 题解和总结:/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>