LeetCode Weekly Contest 147 4問目 - Stone Game II [1140]

Source

LeetCode Weekly Contest 147
問題文

問題概要

省略

解法

省略

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

#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
int N;
int A[100];
int dp[101][101];
int vis[101][101];
int sum[101];
int solve(int c, int m){
  int i, res=0;
  if(vis[c][m]){
    return dp[c][m];
  }
  vis[c][m] = 1;
  if(c==N){
    return dp[c][m] = 0;
  }
  for(i=(1);i<(2*m+1);i++){
    if(c+i > N){
      break;
    }
    chmax(res, (sum[N] - sum[c]) - solve(c+i,max_L(m, i)));
  }
  return dp[c][m] = res;
}
class Solution{
  public:
  int stoneGameII(vector<int>& piles){
    int i, j, res;
    N = piles.size();
    for(i=0;i<(N);i++){
      A[i] = piles[i];
    }
    for(i=0;i<(N+1);i++){
      for(j=0;j<(N+1);j++){
        vis[i][j] = 0;
      }
    }
    sum[0] = 0;
    for(i=0;i<(N);i++){
      sum[i+1] = sum[i] + A[i];
    }
    res = solve(0, 1);
    return res;
  }
}
;

// cLay varsion 20190802-2

// --- original code ---
// int N, A[100];
// int dp[101][101], vis[101][101];
// int sum[101];
// 
// int solve(int c, int m){
//   int i, res = 0;
//   
//   if(vis[c][m]) return dp[c][m];
//   vis[c][m] = 1;
//   
//   if(c==N) return dp[c][m] = 0;
// 
//   rep(i,1,2m+1){
//     if(c+i > N) break;
//     res >?= (sum[N] - sum[c]) - solve(c+i, max(m,i));
//   }
// 
//   return dp[c][m] = res;
// }
// 
// class Solution {
// public:
//   int stoneGameII(vector<int>& piles) {
//     int i, j, res;
// 
//     N = piles.size();
//     rep(i,N) A[i] = piles[i];
// 
//     rep(i,N+1) rep(j,N+1) vis[i][j] = 0;
//     
//     sum[0] = 0;
//     rep(i,N) sum[i+1] = sum[i] + A[i];
// 
//     res = solve(0, 1);
//     return res;
//   }
// };
// 
// {
//   // main関数を適当に処理する
// }

Current time: 2024年04月26日21時03分27秒
Last modified: 2019年08月10日17時12分05秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)