LeetCode Weekly Contest 218 4問目 - Minimum Incompatibility [1681]

Source

LeetCode Weekly Contest 218
問題文

問題概要

省略

解法

省略

cLay（version 20201206-1）のコード

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

#define main dummy_main
{}
#undef main

int dp[1d5];
int ls[20], lis[20][1d5], cost[20][1d5];
int sz, arr[20];

class Solution {
public:
  int minimumIncompatibility(vector<int>& A, int K) {
    int N = A.size(), res, f;
    K = N / K;
    sort(A.begin(), A.end());
    rep(i,N) ls[i] = 0;
    rep(i,1<<N){
      sz = 0;
      rep(j,N) if(BIT_ith(i,j)) arr[sz++] = A[j];
      if(sz != K) continue;
      rep(j,N) if(BIT_ith(i,j)) f = j, break;
      rep(j,1,K) if(arr[j-1] == arr[j]) break_continue;
      arrInsert(ls[f], ls[f], lis[f], i, cost[f], arr[K-1] - arr[0]);
    }

    rep(i,1<<N) dp[i] = int_inf;
    dp[0] = 0;

    rep(mask,(1<<N)-1) if(dp[mask] < int_inf){
      rep(f,N) if(!BIT_ith(mask,f)) break;
      rep(i,ls[f]) if(!(mask & lis[f][i])) dp[mask|lis[f][i]] <?= dp[mask] + cost[f][i];
    }

    res = dp[(1<<N)-1];
    return if[res==int_inf, -1, res];
  }
};

Current time: 2024年04月25日03時30分05秒
Last modified: 2020年12月06日15時13分53秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)