LeetCode Weekly Contest 183 4問目 - Stone Game III [1406]

Source

LeetCode Weekly Contest 183
問題文

問題概要

省略

解法

省略

cLay（version 20200408-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

int N, A[50000];
int dp[50000], sm[50001];

int solve(int dep){
  int res = -int_inf, tmp = 0;
  if(dep >= N) return 0;
  if(dp[dep] != -int_inf) return dp[dep];

  rep(i,3){
    if(dep + i >= N) break;
    tmp += A[dep + i];
    res >?= tmp + sm[dep + i + 1] - solve(dep + i + 1);
  }

  return dp[dep] = res;
}

class Solution {
public:
  string stoneGameIII(vector<int>& stone) {
    int alice, bob;
    N = stone.size();
    rep(i,N) A[i] = stone[i];

    sm[N] = 0;
    rrep(i,N) sm[i] = sm[i+1] + A[i];

    rep(i,N) dp[i] = -int_inf;
    alice = solve(0);
    bob = sm[0] - alice;

    return if[alice > bob, "Alice", alice < bob, "Bob", "Tie"];
  }
};

Current time: 2024年05月09日05時28分17秒
Last modified: 2020年04月10日06時28分48秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)