제출 #239266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239266		Nightlight	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	558 ms	780580 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define RED 0
#define GRE 1
#define YEL 2
using namespace std;

int N;
int memo[405][405][405][3];
int pos[405][3], pre[405][3];
int pr, py, pg;

int dp(int r, int g, int y, int last) {
  if(r == pr && g == pg && y == py) return 0;
  if(memo[r][g][y][last] != -1) return memo[r][g][y][last];
  int res = 1000000000;
  if(r < pr && last != 0) {
    int now = pos[r][0];
    res = min(res, dp(r + 1, g, y, 0) + max(pre[now][1] - g, 0) + max(pre[now][2] - y, 0));
  }
  if(g < pg && last != 1) {
    int now = pos[g][1];
    res = min(res, dp(r, g + 1, y, 1) + max(pre[now][0] - r, 0) + max(pre[now][2] - y, 0));
  }
  if(y < py && last != 2) {
    int now = pos[y][2];
    res = min(res, dp(r, g, y + 1, 2) + max(pre[now][0] - r, 0) + max(pre[now][1] - g, 0));
  }
  return memo[r][g][y][last] = res;
}

int main() {
  memset(memo, -1, sizeof(memo));
  ios_base::sync_with_stdio(0);
  cin >> N;
  char ch;
  for(int i = 1; i <= N; i++) {
    cin >> ch;
    if(ch == 'R') {
      pre[i][0] = 1;
      pos[pr++][0] = i;
    }else if(ch == 'G') {
      pre[i][1] = 1;
      pos[pg++][1] = i;
    }else {
      pre[i][2] = 1;
      pos[py++][2] = i;
    }
    pre[i][0] += pre[i - 1][0];
    pre[i][1] += pre[i - 1][1];
    pre[i][2] += pre[i - 1][2];
  }
  int ans = 1000000000;
  if(pr > 0) {
    int now = pos[0][0];
    ans = min(ans, dp(1, 0, 0, 0) + pre[now][1] + pre[now][2]);
  }
  if(pg > 0) {
    int now = pos[0][1];
    ans = min(ans, dp(0, 1, 0, 1) + pre[now][0] + pre[now][2]);
  }
  if(py > 0) {
    int now = pos[0][2];
    ans = min(ans, dp(0, 0, 1, 2) + pre[now][0] + pre[now][1]);
  }
  if(ans != 1000000000) {
    cout << ans << "\n";
  }else cout << "-1\n";
  cin >> N;
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25