2020/10/31

ARC107 D

分数を管理するのは嫌な気持ちになる

→先に2^(十分大きい数)を掛けておく?

→DPの状態数が破滅

2倍すると再帰的になることに気づいていなかった(結局分割数のようなものを求めたいので、同様の方針で考えるべきだった)

 

 

今まで使った数の最大値(or最小値)を持っておくことで重複を除くDP(使う数にA<Bのような条件を付けて状態を区別したい時)

→うまいこと式変形をして、条件を0<B-Aの形にすると遷移が綺麗になることがある

 

分割数DPの場合

例えば1+2+1と1+1+2を同一視したい、昇順のものだけ数えることにすると

→dp[i][j][k]:=0~kまでの数で、iをj分割する方法 

Aの分を先に足しておくことにして0<A型の条件にすることを考える

dp[i][j]:=i個の区別できない玉を、j個の区別できない場合箱に入れる場合の数とする

ある分割に対して、箱を持っていない状態から初めて、先頭に箱を一つ追加する操作、持っている箱すべてに玉を入れる操作の操作列は一対一対応する、よって

dp[i+j][j]+=dp[i][j] (全てに玉を入れる操作)

dp[i][j+1]+=dp[i][j] (箱を増やす操作)

 

 

この問題の場合、1を足す操作、今までに足した数を/2する操作の操作列に言い換えられる、よってdp[i要素][総和j]:=として

dp[i+1][j+1]+=dp[i][j]

dp][i][j/2]+=dp[i][j] (j=0 mod2)