Codeforces Global Round 4 F1問題 - Short Colorful Strip

Source

Codeforces Global Round 4 F1問題 (1500pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20190721-1)のコード

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

//no-unlocked
#define MD 998244353

int N;
int C[500];

int vis[500][500];
mint dp[500][500];

mint solve(int a, int b){
  int i, j, k;
  mint lef, rig;

  if(a > b) return 1;
  if(vis[a][b]) return dp[a][b];
  vis[a][b] = 1;

  j = int_inf;
  rep(i,a,b+1) if(j > C[i]){
    j = C[i];
    k = i;
  }

  lef = rig = 0;
  for(i=k;i>=a;i--) lef += solve(a,i-1) * solve(i,k-1);
  for(i=k;i<=b;i++) rig += solve(k+1,i) * solve(i+1,b);
  
  return dp[a][b] = lef * rig;
}

{
  mint res;
  rd(N,N,C(N));
  res = solve(0, N-1);
  wt(res);
}

Current time: 2022年05月18日08時47分16秒
Last modified: 2019年07月21日15時49分17秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces Codeforces_Global_Round_4
トップページに戻る

Logged in as: unknown user (not login)

ログイン: