LeetCode Weekly Contest 146 3問目 - Minimum Cost Tree From Leaf Values [1130]

Source

LeetCode Weekly Contest 146
問題文

問題概要

省略

解法

省略

cLay（version 20190721-1）のコード [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 chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
int N;
int A[40];
int dp[40][40];
int mx[40][40];
long long solve(int a, int b){
  int i, res=1073709056;
  if(dp[a][b] >= 0){
    return dp[a][b];
  }
  if(a==b){
    return dp[a][b] = 0;
  }
  for(i=a;i<b;i++){
    chmin(res, solve(a,i) + solve(i+1,b) + mx[a][i] * mx[i+1][b]);
  }
  return dp[a][b] = res;
}
class Solution{
  public:
  int mctFromLeafValues(vector<int>& arr){
    int i, j;
    N = arr.size();
    for(i=0;i<N;i++){
      A[i] = arr[i];
    }
    for(i=0;i<N;i++){
      for(j=0;j<N;j++){
        dp[i][j] = -1;
      }
    }
    for(i=0;i<N;i++){
      mx[i][i] = A[i];
      for(j=i+1;j<N;j++){
        mx[i][j] =max_L(mx[i][j-1], A[j]);
      }
    }
    return solve(0, N-1);
  }
}
;

// cLay varsion 20190721-1

// --- original code ---
// int N, A[40];
// int dp[40][40];
// int mx[40][40];
// 
// ll solve(int a, int b){
//   int i;
//   int res = int_inf;
//   
//   if(dp[a][b] >= 0) return dp[a][b];
//   if(a==b) return dp[a][b] = 0;
//   
//   rep(i,a,b) res <?= solve(a,i) + solve(i+1,b) + mx[a][i] * mx[i+1][b];
// 
//   return dp[a][b] = res;
// }
// 
// class Solution {
// public:
//   int mctFromLeafValues(vector<int>& arr) {
//     int i, j;
//     N = arr.size();
//     rep(i,N) A[i] = arr[i];
//     rep(i,N) rep(j,N) dp[i][j] = -1;
//     rep(i,N){
//       mx[i][i] = A[i];
//       rep(j,i+1,N) mx[i][j] = max(mx[i][j-1], A[j]);
//     }
//     return solve(0, N-1);
//   }
// };
// 
// {
//   // main関数を適当に処理する
// }

Current time: 2024年04月27日03時47分06秒
Last modified: 2019年07月22日08時00分29秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)