D: ダルマ落とし
問題
長さnの数列aが与えられる。次の操作を好きなだけ繰り返す。
- 数列の任意の隣り合う2数を一つ選び、その差の絶対値が1以下ならばその2数を数列から取り除き、数列は詰めて長さが2短くする
最大で幾つ取り除くことができるか。
制約
テストケース <= 50
n <= 300
解法
区間DP。以下、左閉右開区間[i, j) i以上j未満の区間を使って説明する。
dp[i][j] := 区間[i, j)の数列に対して、この区間だけで取り除くことができる最大の個数
とする。重要なのはdp[i][j]を計算するのには、その外側の区間は全く関係無いということ。
dp[i][j]とdp[j][k]がわかっているとすると、この区間を並べて[i, k)が考えられる。 つまり
for j in { i+1 <= j <= k-1 }: dp[i][k] は dp[i][j] + dp[j][k] 以上
dp[i][k]が2つに分けることができないパターンとして、 A[i]とA[k-1]を同時に取り除く場合がある。
ただし、[i+1, k-1)が全て取り除くことができないなら、A[i], A[k-1]のペアを取り除くことはできない。
if |A[i] - A[k-1]| <= 1 and dp[i+1][k-1] == k-i-2: dp[i][k] = k - i
取り除き方はこれで全て列挙されている。このことから、[i, k)を計算するにはその間の小さい区間が全て計算されていればいい。
これを区間DPと呼ぶ、わかりにくいなら再帰関数で書けばいい。
三重ループで書くと
for l in 1 .. n: for i in 1 .. n: for j in i .. i+l: dp[i][i+l] は dp[i][j] + dp[j][i+l] 以上 ...
のように、外側から、長さ・左端のインデックス・中間のインデックスとできる。速さを意識するなら、2次配列の1番目のインデックスのループをなるべく外側にするとよい。
for i in n-1 .. 0: for j in i+1 .. n: for k in j+1 .. k: dp[i][k] は dp[i][j] + dp[j][k] 以上 ...
コード
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } int N, W[311]; int dp[311][311]; int main() { while (scanf("%d", &N), N) { REP (i, N) scanf("%d", W + i); memset(dp, 0, sizeof dp); for (int i=N-1; i>=0; i--) { dp[i][i] = 0; dp[i][i+1] = 0; for (int j=i+1; j<=N; j++) { if (i + 1 < j && abs(W[i] - W[j-1]) <= 1 && dp[i+1][j-1] == j-i-2) dp[i][j] = j - i; for (int k=j+1; k<=N; k++) amax(dp[i][k], dp[i][j] + dp[j][k]); } } printf("%d\n", dp[0][N]); } return 0; }
日記
この辺りから高校数学の知識だけでは難しくなる。メモリを潤沢に使うことで性能の高いアルゴリズムを得る。