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;
}