LeetCode Weekly Contest 215 4問目 - Maximize Grid Happiness [1659]

Source

LeetCode Weekly Contest 215
問題文

問題概要

省略

解法

省略

cLay（version 20201115-2）のコード

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

#define main dummy_main
{}
#undef main

int fg;
int answer[6][6][7][7];
int dp[7][7][243], nx[7][7][243], pw[7];

void solve(void){
  const int a = 6, b = 6;
  int pr[7], i, j, k, ni, nj, nc, m, nm, n1, n2;

  fg = 1;
  pw[0] = 1;
  rep(i,1,7) pw[i] = 3 * pw[i-1];

  rep(y,1,6){
    rep(i,a+1) rep(j,b+1) rep(k,pw[y]) dp[i][j][k] = -int_inf;
    dp[0][0][0] = 0;
    rep(x,1,6){
      rep(m,y){
        rep(i,a+1) rep(j,b+1) rep(k,pw[y]) nx[i][j][k] = -int_inf;
        rep(i,a+1) rep(j,b+1) rep(k,pw[y]) if(dp[i][j][k] > -int_inf){
          DigitF(k,y,pr,3);
          rep(l,3){
            ni = i + if[l==1, 1, 0];
            nj = j + if[l==2, 1, 0];
            if(ni > a || nj > b) continue;
            nm = (k * 3) % pw[y] + l;
            nc = dp[i][j][k];
            n1 = n2 = 0;
            if(l){
              if(m && pr[0]==1) n1++;
              if(m && pr[0]==2) n2++;
              if(pr[y-1]==1) n1++;
              if(pr[y-1]==2) n2++;
              nc += n1 * (-30) + n2 * 20 + (n1 + n2) * (if[l==1, -30, 20]);
            }
            nx[ni][nj][nm] >?= nc;
          }
        }
        rep(i,a+1) rep(j,b+1) rep(k,pw[y]) dp[i][j][k] = nx[i][j][k];
      }
      rep(i,a+1) rep(j,b+1) rep(k,pw[y]) answer[x][y][i][j] >?= dp[i][j][k] + 120 * i + 40 * j;
    }
  }

  rep(x,1,6) rep(y,1,6) rep(i,a+1) rep(j,b+1){
    if(i) answer[x][y][i][j] >?= answer[x][y][i-1][j];
    if(j) answer[x][y][i][j] >?= answer[x][y][i][j-1];
  }
}

class Solution {
public:
  int getMaxGridHappiness(int x, int y, int a, int b) {
    if(!fg) solve();
    return answer[x][y][a][b];
  }
};

Current time: 2024年04月26日23時01分34秒
Last modified: 2020年11月15日17時29分39秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)