LeetCode Weekly Contest 368 4問目 - Minimum Changes to Make K Semi-palindromes [2911]

Source

LeetCode Weekly Contest 368
問題文

問題概要

省略

解法

省略

cLay（version 20231031-1）のコード

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

#define main dummy_main
{}
#undef main

int calc(const string &s){
  int N = s.size(), res = int_inf, k;
  rep(k,1,N) if(N%k==0) res <?= sum[i,0,k]( PalindromeCost(Slice(s,i,N,k)) );
  return res;
}

class Solution {
public:
  int minimumChanges(string s, int k) {
    int i, j, N = s.size();
    static ll cost[201][201], dp[201];

    rep(i,N) rep(j,i,N) cost[i][j] = calc(s.substr(i,j-i+1));

    dp[0] = 0;
    rep(i,1,N+1) dp[i] = ll_inf;

    rep(k){
      rrep(i,N+1){
        dp[i] = ll_inf;
        rep(j,i) dp[i] <?= dp[j] + cost[j][i-1];
      }
    }

    return dp[N];
  }
};

Current time: 2024年05月05日23時46分36秒
Last modified: 2023年11月03日19時49分24秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)