Codeforces Round #243 (Div. 2) E. Sereja and Two Sequences DP

链接：

http://codeforces.com/contest/426/problem/E

题意：

两组数字a和b 如果a[i]等于b[j] 则可将a[i]和b[j]前所有数字删掉这种操作花费e体力得到1元钱

或者一次删掉所有数字这种操作花费等于曾经删除的所有数字个数做完后得到所有钱

一共s体力最多可以得到多少钱

题解：

dp+二分

由数据可知最多拿到300元钱因此可以定义 dp[i][j]表示有i元钱时 b串删除到了j处时 a串删到的位置

状态转移为 dp[i][j] = lower_bound ( a[j] , dp[i-1][j-1] + 1 ) 意思是a[j]与dp[i-1][j-1]后的第一个相同的数字匹配

代码：

31 int n, m, s, e;
32 int a[MAXN], b[MAXN];
33 int dp[310][MAXN];
34 VI v[MAXN];
35  
36 int main() {
37     ios::sync_with_stdio(false), cin.tie(0);
38     cin >> n >> m >> s >> e;
39     rep(i, 1, n + 1) cin >> a[i];
40     rep(i, 1, m + 1) {
41         cin >> b[i];
42         v[b[i]].pb(i);
43     }
44     rep(i, 0, MAXN) v[i].pb(INF);
45     memset(dp, 0x3f, sizeof(dp));
46     memset(dp[0], 0, sizeof(dp[0]));
47     int ans = 0;
48     rep(i, 1, s / e + 1) rep(j, 1, n + 1) if (dp[i - 1][j - 1] != INF) {
49         dp[i][j] = dp[i][j - 1];
50         int k = *lower_bound(all(v[a[j]]), dp[i - 1][j - 1] + 1);
51         if (k == INF) continue;
52         dp[i][j] = min(dp[i][j], k);
53         if (dp[i][j] + j + i*e <= s) ans = max(ans, i);
54     }
55     cout << ans << endl;
56     return 0;
57 }