結果
問題 |
No.2374 ASKT Subsequences
|
ユーザー |
|
提出日時 | 2023-07-08 00:46:25 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 492 ms / 2,000 ms |
コード長 | 1,342 bytes |
コンパイル時間 | 1,670 ms |
コンパイル使用メモリ | 174,188 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-21 21:07:00 |
合計ジャッジ時間 | 16,564 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
import std; // 解説AC 部分列を捜査するという時点で基本的には全探索しかないため、DPっぽいなーっていうのは気づいていた。 // ただ、Kの値を固定できたらなーっていう考えに気づくのが遅すぎたため、既存の方針で何とかできないか考えてしまった。 void main () { int N = readln.chomp.to!int; int[] A = readln.split.to!(int[]); long ans = 0; foreach (K; 1..2001) { ans += solve(N, A, K); } writeln(ans); } auto solve (int N, int[] A, int K) { // Kさえ固定できてしまえば更新がだいぶんさぼれるぞい const sup = 2001; // dp[j][k] := i項目まで見たとき、a_1がjである部分列のk個目をとれる場合の数 long[][] dp = new long[][](sup, 4); // initialize dp[A[0]][0] = 1; foreach (i; 1..N) { // K==3 if (1 <= A[i]-K-11) { dp[A[i]-K-11][3] += dp[A[i]-K-11][2]; } // K==2 if (1 <= A[i]-10) { dp[A[i]-10][2] += dp[A[i]-10][1]; } // K==1 if (1 <= A[i]-K-10) { dp[A[i]-K-10][1] += dp[A[i]-K-10][0]; } // K==0 dp[A[i]][0]++; } long res = 0; foreach (j; 1..sup) { res += dp[j][$-1]; } return res; }