CF原题
由题可知，n,m太大，无法开出dp[n][m]的数组。
观察发现s/e最大为300，也就是说，选用第一种操作的次数不会超过300。
于是定义dp[i][j],第一个串的前i个数，使用了j次第一种操作的时候，第二个串最少删了多少个数。
转移有两种情况：
1.当前位置不删，这时dp[i][j]=dp[i-1][j]；
2.当前位置删，此时就需要在B串中找和当前位置的数相同的数的位置，并且只有在找到的位置大于dp[i-1][j-1]的时候才是可行的。为了保证dp[i][j]最小，显然就是找大于dp[i-1][j-1]这个位置的第一个和当前数相同的数。
二分查找解决，lower_bound或upper_bound解决更加简便。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define Mod 1000000007
using namespace std;
#define N 100007 int dp[N][];
int a[N],b[N];
vector<int> v[N]; int main()
{
int n,m,s,e;
int i,j;
scanf("%d%d%d%d",&n,&m,&s,&e);
for(i=;i<=n;i++)
scanf("%d",&a[i]);
for(i=;i<=m;i++)
{
scanf("%d",&b[i]);
v[b[i]].push_back(i);
}
int S = s/e;
for(i=;i<=n;i++)
{
dp[i][] = -;
for(j=;j<=S;j++)
dp[i][j] = Mod;
}
for(i=;i<=m;i++) //a的第一个对应的最小位置
{
if(b[i] == a[])
{
dp[][] = i;
break;
}
}
//meiju
vector<int>::iterator it;
for(i=;i<=n;i++)
{
for(j=;j<=S;j++)
{
dp[i][j] = min(dp[i][j],dp[i-][j]); //当前位置不删
it = upper_bound(v[a[i]].begin(),v[a[i]].end(),dp[i-][j-]);
if(it != v[a[i]].end()) //如果能找到，更新最小位置
dp[i][j] = min(dp[i][j],*it);
}
}
int res = -Mod;
for(i=;i<=n;i++)
{
for(j=;j<=S;j++)
{
if(i + dp[i][j] + j*e <= s) //满足能量范围
res = max(res,j);
}
}
printf("%d\n",res);
return ;
}