AtCoder Beginner Contest 176 F問題 - Brave CHAIN

Source

AtCoder Beginner Contest 176
問題文

問題概要

省略

解法

省略

cLayversion 20200911-1)のコード

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

int N, A[6000];
int dp[2000][2000], mx, mx1[2000];
int bf[2000][2000], bmx, bmx1[2000];

void change(int i, int j, int v){
  (dp[i][j], dp[j][i], mx1[i], mx1[j], mx) >?= v;
}

{
  int a[3], x, y, z;
  int res = 0, ad = 0;
  rd(N,(A--)(3N));

  (x, y, z) = (A[0], A[1], A[3N-1]);

  rep(i,N) mx1[i] = -int_inf;
  rep(i,N) rep(j,N) dp[i][j] = -int_inf;
  change(x, y, 0);
  rep(k,N-1){
    rep(i,3) a[i] = A[3*k+2+i];
    sort(a, a+3);
    if(a[0]==a[2]) ad++, continue;
    if(a[1]==a[2]) swap(a[0], a[2]);

    bmx = mx;
    rep(i,N) bmx1[i] = mx1[i];
    rep(i,N) bf[i][a[0]] = dp[i][a[0]];
    rep(i,3) bf[a[i]][a[i]] = dp[a[i]][a[i]];
    
    rep(j,3) rep(i,N) change(a[j], i, bmx1[i]);
    rep(i,3) rep(j,i+1,3) change(a[i], a[j], bmx);
    if(a[0]==a[1]) rep(i,N) change(i, a[2], bf[i][a[0]] + 1);
    rep(i,3) change(a[(i+1)%3], a[(i+2)%3], bf[a[i]][a[i]] + 1);
  }
  res = max(mx, dp[z][z] + 1);
  wt(res + ad);
}

Current time: 2021年09月19日21時20分45秒
Last modified: 2020年09月11日07時30分10秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC176 ABC_F
トップページに戻る

Logged in as: unknown user (not login)

ログイン: