2020年12月05日15時22分05秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
Codeforces Round #688 DIV2 F問題 (3500pt)
Problem description
省略
省略
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日20時23分59秒
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)