問題文DP強化週間。長さNの数列が与えられる。数字間を+か-で計算していき、 その結果がKで割り切れるか調べよ、という問題。いかにもなDP。雪だるま式に書くより、メモ化再帰の方が直感的だった。他の人は雪だるま式に書いてるとこが多いみたい。 dp[i+1][j…

問題文DP強化週間。一列に兵が並んでおり、ここから何人か除いた時に、 残りの兵いずれもが少なくとも隊列の左右のどちらかの 端(端の兵ではない)が見通せるようにしたい。端が見通せる条件は 端までに自分より同じか背の高い兵が一人もいない時とする。 取…

問題文DP強化週間。stringが2つ与えられる。LCS長を求めよ。dp[i + 1][j + 1]:=(文字列1のi番目までと文字列2のj番目までのLCS長)でDP。以下ソース。 int dp[1001][1001]; int main(){ string s, t; while(cin >> s >> t){ memset(dp, 0, sizeof(dp)); int N…

問題文DP強化週間。花がF種類あって、一列に並んだ花瓶がV個ある。 花iは花i+1より左側の花瓶に活ける必要がある。 花の種類と各花瓶に対応した点数が与えられる。 点数を最大化せよ。という問題。dp[i + 1][j + 1]:=(花iまでを花瓶jまでにいけた時の最大の…

問題文DP強化週間。蟻の家族がいくつか与えられる。家族iはa[i]匹からなる。 この蟻の群れからS ~ B匹選ぶときの（順番を区別しない）集合の数を数えよ。重複組み合わせ。蟻本にまったく同じものがあったので参考にした。 dp[i][j]:=(家族i - 1まででj匹選ぶ…

問題文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…

問題文 生徒が車座に座り、各人に偶数個のキャンディが与えられる。先生の合図で、生徒は自分の持っているキャンディの半分を右にいる生徒に同時に渡す。その後キャンディが奇数個になった生徒にはキャンディが1つ追加される。この作業を全ての生徒のキャン…

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

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

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