제출 #572413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572413		SSRS	스카이라인 (IZhO11_skyline)	C++14	100 / 100	108 ms	50188 KiB

skyline

#include <bits/stdc++.h>
using namespace std;
const int INF = 10000000;
int main(){
  int N;
  cin >> N;
  vector<int> h(N);
  for (int i = 0; i < N; i++){
    cin >> h[i];
  }
  vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(201, vector<int>(201, INF)));
  dp[0][0][0] = 0;
  for (int i = 0; i < N; i++){
    for (int j = 0; j <= h[i]; j++){
      for (int k = j; k <= 200; k++){
        dp[i + 1][k - j][h[i] - j] = min(dp[i + 1][k - j][h[i] - j], dp[i][j][k] + j * 7);
      }
    }
    for (int j = 200; j >= 0; j--){
      for (int k = 199; k >= 0; k--){
        if (j < 200){
          dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i + 1][j + 1][k + 1] + 5);
        }
        dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i + 1][j][k + 1] + 3);
      }
    }
  }
  cout << dp[N][0][0] << endl;
}

• Subtask 1: 100 / 100