モノグサプログラミングコンテスト2022 (ABC238) F - Two Exams (500)
最初の考察
存在してはいけない組み合わせの所に辺を張る
$ 2^{自身の後ろにある点の数}だけ作ってはいけないパターンがある
グラフがダイアモンド継承みたいになっていると重複が発生するので駄目
最終的な考察
Pの昇順にソートして考える
この配列を後ろから見ていったときにある$ Q_iの人$ iを選んだ場合、それ以前の$ Q_j \lt Q_iな人$ jは必ず選ばないといけない
$ dp[i][j][l] で$ i人目まで見て$ j人選んでその内のQの最大値が$ lの場合の個数とする
初期値は$ dp[n-1][0][0] = 1, dp[n-1][1][a_{n-1}] = 1
遷移は、
$ dp[i][j+1][\max(l,a_i)] += dp[i+1][j][l] と、$ dp[i][j][l] += dp[i+1][j][l] の2つ
$ \sum_l dp[0][k][l] が答え
時間計算量は$ \mathcal{O}(N^2 K)