まぁこれはゴリ押しがきくかな。
https://atcoder.jp/contests/past15-open/tasks/past202306_m
問題
1次元の数直線上にN個の点がある。
i番と(i+1)番の点の距離D(i)が与えられたとき、1番とN番の点の距離の最小値を求めよ。
解法
dp(n,x) := 1番目の点を位置0に置き、番号の小さい順に場所を確定させたとき、n番目の点を位置xに置けるか
とすると
dp(n+1,x) = dp(n,x-D[n]) or dp(n,x+D[n])
となる。bitsetであればこれらを短時間で処理できる。
int N; bitset<4040400> BS; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; BS[2020200]=1; FOR(i,N-1) { cin>>x; BS=(BS>>x)|(BS<<x); } int mi=1<<30; FOR(i,4040400) if(BS[i]) mi=min(mi,abs(i-2020200)); cout<<mi<<endl; }
まとめ
Bitsetを使う典型問題。