ICPC2017 国内予選 D 弁当作り

AOJ ICPC 動的計画法

問題

各成分が0, 1であらわされる行列Aが与えられる。
Aの行の部分集合A[i]で、任意の列jに対してΣi_s[i][j]が偶数になるものを考える。
このようなA[i]のうち最大のサイズはいくつか。


例）Aが
010
011
110
101
だったら、2, 3, 4行目を選ぶと全ての列の和が偶数になり、このときの3つが最大。

制約条件

Aをn行m列としたときn, m≦500, nm≦500

続きを読む

TopCoder SRM 622 Div1 Hard

TopCoder 文字列 データ構造

問題

aまたはbからなる文字列が与えられる。
このとき、文字列に2回以上、重ならないで出現する空でない部分文字列の個数を求めよ。
文字列が同じときは一つと数える。

制約条件

文字列は乱数により生成される。
n≦10^5

続きを読む

Codeforces 480(#274 Div1) D. Parcels

Codeforces 動的計画法

問題

n個の箱があり、i番目の箱は
時刻in[i]に倉庫に入り、out[i]に倉庫から出る。
この荷物は重さがw[i]であり、上にs[i]までの荷物を載せることができる。
この荷物を倉庫に出し入れするとv[i]円もらえる。


倉庫には、同時に全体でSの重さの荷物しか入れられない。
また、荷物は直前に入れた荷物の真上にのみ置くことができ、最も上にある荷物のみを取り出すことができる。


利益を最大にするように、倉庫に出し入れする荷物を選択したときの利益を求めよ。

制約条件

n≦500
0≦in[i]＜out[i]＜2*n
w[i], s[i], S≦1000
v[i]≦10^6

続きを読む