LeetCode Weekly Contest 175 4問目 - Maximum Students Taking Exam [1349]

Source

LeetCode Weekly Contest 175
問題文

問題概要

省略

解法

省略

cLayversion 20200214-1)のコード

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

#define main dummy_main
{}
#undef main

int X, Y, S[8][8];
int dp[8][257];
int sz, pt[257];

int solve(int dep, int up){
  int res = 0, tmp;

  if(dep==X) return 0;
  if(dp[dep][up] >= 0) return dp[dep][up];

  rep[pt](mask,sz){
    tmp = 0;
    rep(i,Y) if(mask & 1<<i){
      tmp++;
      if(S[dep][i]) break_continue;
      if(i-1 >= 0 && (up & 1<<(i-1))) break_continue;
      if(i+1 <  Y && (up & 1<<(i+1))) break_continue;
    }
    tmp += solve(dep+1, mask);
    res >?= tmp;
  }
  return dp[dep][up] = res;
}

class Solution {
public:
  int maxStudents(vector<vector<char>>& seats) {
    X = seats.size();
    Y = seats[0].size();
    rep(i,X) rep(j,Y) S[i][j] = if[seats[i][j]=='.', 0, 1];
    rep(i,X) rep(j,1<<Y) dp[i][j] = -1;

    sz = 0;
    rep(mask,1<<Y){
      rep(i,Y-1) if((mask & 1<<i) && (mask & 1<<(i+1))) break_continue;
      pt[sz++] = mask;
    }

    return solve(0,0);
  }
};

Current time: 2024年03月29日08時24分15秒
Last modified: 2020年02月16日01時28分30秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)

ログイン: