Codeforces 425(#243 Div1) C. Sereja and Two Sequences
問題
二つの数列が与えられる。
この数列に次の2種類の操作を行える。
- 両方の数列から、空でない任意のprefixを選んで削除する。ただし両方のprefixの、最後の要素は一致していなければならない。
- 残った数列を全て削除する。
1番目の操作にかかるコストはe, もらえる得点は1
2番目の操作にかかるコストは1番の操作で消した要素の数の合計に等しい。
使えるコストは全部でsで、最後に2番の操作を行わないと得点は0になる。
このとき得られる最大の得点を求めよ。
制約条件
n, m≦10^5
s≦3*10^5
10^3≦e≦10^4
方針
誤読してムリゲーだと思っていたシリーズ。
s / eが300くらいなので、1の操作は300回くらいしかできない。
二つの数列をA, Bとする。
i回消したときの数列Bを消した個数の最小値をdp[i]として、
これを更新するDPをする。
Aのそれぞれの要素に対してdpをループさせて見るので、
ループの回数はO(ns/e)回くらい。
A[i]と同じ要素を探すのに、setなどのデータ構造を使うと、ここにlogmがかかるが、間に合う。
ソースコード
const int MX = 100010; int n, m, s, e; int a[MX], b[MX]; int dp[MX]; //dp[最大回数]: 最小位置 int main(){ cin >> n >> m >> s >> e; rep(i, n) cin >> a[i]; rep(i, m) cin >> b[i]; set<pi> bs; rep(i, m) bs.insert(mp(b[i], i)); int ans = 0; int lim = s / e; rep(i, lim + 1) dp[i] = inf; dp[0] = -1; rep(i, n) for(int j = lim; j >= 0; j--) if(dp[j] < inf){ set<pi>::iterator it = bs.lower_bound(mp(a[i], dp[j] + 1)); if(it != bs.end() && it->first == a[i]){ dp[j + 1] = min(dp[j + 1], it->second); int cost = i + it->second + 2; if(cost + (j + 1) * e <= s) ans = max(ans, j + 1); } } cout << ans << endl; return 0; }