[JOI精進録] 難易度7「IOI列車で行こう」(第12回日本情報オリンピック 本選B)

問題リンク

atcoder.jp

問題概要

2つの文字列、がある。
文字列からそれぞれ先頭何文字かを無視し、その後の文字列について以下を考える。
・I、O、I、O、...、Iとなるように文字列の先頭から一文字ずつ取り出して構成していったときの最大の構成できる長さ
適切に無視する長さと取り出す順番を考えたとき、最大の長さを出力してください。

解説

AC解法 (100/100点)

の先頭文字、の先頭文字を考えて最後の文字がになるように構成したときの最大の長さ
として、条件を満たすようにDPテーブルを更新していきます。

ACコード

#include <bits/stdc++.h>
using namespace std;
// dp[i][k][o] = Sから先頭iTから先頭kを待機または編成して最後がo[1:i 0:o]のときできる最大の編成長
int main(){
  int n, m, r(0); string s,t; cin >> n >> m >> s >> t;
  vector dp(n+1,vector(m+1,vector(2,0)));
  for (int i(0);i <= n;++i) for (int k(0);k <= m;++k){
    if (i==k&&i==0) continue;
    if (k!=0) dp[i][k][t[k-1]=='I']=max(dp[i][k][t[k-1]=='I'],dp[i][k-1][t[k-1]=='O']+max((bool)dp[i][k-1][t[k-1]=='O'],t[k-1]=='I'));
    if (k!=0&&t[k-1]=='I') r = max(r,dp[i][k][1]);
    if (i!=0) dp[i][k][s[i-1]=='I']=max(dp[i][k][s[i-1]=='I'],dp[i-1][k][s[i-1]=='O']+max((bool)dp[i-1][k][s[i-1]=='O'],s[i-1]=='I'));
    if (i!=0&&s[i-1]=='I') r = max(r,dp[i][k][1]);
  }
  cout << r << endl;
}

提出結果

atcoder.jp