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…

int main(){ int a,b,c,n; cin >> n >> a >> b >> c; int ret = 0; for(int i = 0; i <= 4000 / a; i++){ for(int j = 0; j <= 4000 / b; j++){ if((n - a * i - b * j) >= 0 && (n - a * i - b * j) % c == 0){ ret = max(ret, i + j + (n - a * i - b * j)…