保存されている過去のバージョンの一覧

2020年12月05日15時22分05秒

Codeforces Round #688 DIV2 F問題 - Even Harder

Source

Codeforces Round #688 DIV2 F問題 (3500pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20201205-1）のコード

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

//no-unlocked
int N, A[3000], tmp[3000];
int dp[3001][3001], dl[3001][3001];
vector<int> en[3001];

int solve(int s, int g){
  int res = int_inf, i, j, k;

  if(dp[s][g] >= 0) return dp[s][g];
  if(s==0) return 0;

  if(s+1 < g) res <?= solve(s, g-1);
  rep(j,en[g-1].size()){
    i = en[g-1][j];
    if(i < s) res <?= solve(i, s) + dl[i+1][s];
  }

  return dp[s][g] = res;
}

{
  REP(rd_int()){
    rd(N,A(N));
    rep(i,N+1) rep(j,N+1) dp[i][j] = -1;
    rep(k,N){
      dl[k][k] = 0;
      rrep(i,k){
        dl[i][k] = dl[i+1][k];
        if(i + A[i] >= k) dl[i][k]++;
      }
    }
    rep(i,N) en[i].clear();
    rep(i,N) en[i+A[i]].push_back(i);
    wt(solve(N-1,N));
  }
}

Current time: 2024年04月20日08時00分51秒
Last modified: 2020年12月05日15時22分05秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF688 CF_DIV2_F
トップページに戻る

Logged in as: unknown user (not login)

ログイン：