問題文DP強化週間。 問題・コードともにPOJ 2593にほぼ同じ。入力形式が違うだけ。ソースは略。

問題文DP強化週間。要素数Nの配列a[]が与えられた時、 のSを求める。N dp[i]:=（i番目までで最大の区間和）とする。これを配列の左端から計算したものdp_lと 右端から計算したdp_rを求め、iを走査してmax(dp_l[i] + dp_r[i + 1])を求めれば良い。 int l[1000…

問題文 DP強化週間。色付きの衣類の、それを洗う時間とその色が入力として与えられる。洗う人が二人いて、同じ色の衣服は二人が同じ時間（区間）にいっぺんに全て洗う必要がある。つまり、片方が洗い終わってももう片方が終わるのを待つ必要がある。また同一…

問題文DP強化週間。 目標金額と使用できる硬貨の単位とその枚数が与えられ、目標の金額を超えずになるべく近く払おうとするときその金額を答える問題。1742 Coins に酷似している。 dp[i]:=(金額iを払おうとするときに余るコインの枚数)でDP。アリ本に同じ問…

DP強化週間。 A,C,G,Tからなる文字列が2つ与えられて、文字列に'-'をいくつか挿入して2つの文字列を同じ長さにする。ただし2つの文字列の同じ位置に'-'は来ないようにする。文字間の対応にはスコアが与えられる。このスコアを最大化するような対応を見つけ、…

DP強化週間。 二次元配列が渡され、和が最大となるような部分長方形を求め、その和を出力する問題。普通にDPするとO(N^4)になるのでだめ。 配列のj行目から一行ずつtmpに足していき、一行足すたびにtmpの部分配列の最大和を求めて、それらのなかでの最大値を…

DP強化週間。 文字列A,B,Cが与えられて、A,Bをそれぞれの文字順序を守って組み合わせた時、Cが得られるか判定する。dp[i][j]:=(Aをi文字、Bをj文字使ってCの冒頭i+j文字の文字列を作れるか否か)のbool DP。 bool dp[201][201]; int main(){ int n; cin >> n;…

DP強化週間。 与えられた文字列にあらたな文字を挿入して回文にするときに必要となる 最小の文字数。dp[i][j] := (str[i...j]を回文とするのに必要な最小文字数)でDP。 intだとMLE。 short dp[5001][5001]; int main(){ int N; string s; cin >> N; cin >> s…