LeetCode Weekly Contest 143 3問目 - Filling Bookcase Shelves [1105]

Source

LeetCode Weekly Contest 143
問題文

問題概要

省略

解法

省略

cLay（version 20190630-1）のコード [C++に変換後]

#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
class Solution{
  public:
  int minHeightShelves(vector<vector<int>>& books, int W){
    int N=books.size(), dp[1001], i, j, k, m, s;
    for(i=0;i<N+1;i++){
      dp[i] = 1073709056;
    }
    dp[0] = 0;
    for(i=0;i<N;i++){
      s = 0;
      m = 0;
      for(j=i;j<N;j++){
        s += books[j][0];
        chmax(m, books[j][1]);
        if(s > W){
          break;
        }
        chmin(dp[j+1], dp[i] + m);
      }
    }
    return dp[N];
  }
}
;
// cLay varsion 20190630-1

// --- original code ---
// class Solution {
// public:
//   int minHeightShelves(vector<vector<int>>& books, int W) {
//     int i, j, k, s, m;
//     int N = books.size();
//     int dp[1001];
// 
//     rep(i,N+1) dp[i] = int_inf;
//     dp[0] = 0;
// 
//     rep(i,N){
//       s = 0;
//       m = 0;
//       rep(j,i,N){
//         s += books[j][0];
//         m >?= books[j][1];
//         if(s > W) break;
//         dp[j+1] <?= dp[i] + m;
//       }
//     }
// 
//     return dp[N];
//   }
// };
// {
//   // main関数を適当に処理する
// }

Current time: 2024年04月20日22時01分31秒
Last modified: 2019年07月01日01時17分43秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)