testB
输入文件: testB.in 输出文件testB.out 时限2000ms
问题描述：
方师傅有两个由数字组成的串 a1,a2,⋯,an 和 b1,b2,⋯,bm。有一天，方师傅感到十分无聊因此他决定用这两个串来玩玩游戏。游戏规则十分简单，方师傅会进行一些操作，每个操作可能是以下两种操作之一：
1.从a串选择一个a的非空前缀，再从b串选一个b的非空前缀。这两个前缀的最后一个元素必须相等，完成选择后把这两个前缀删除。
2.删除两个串所有的元素。
第一种操作会耗费e的能量值，并为方师傅增加一美分到他的电子账户中。第二种操作会耗费两个串的不完整度的能量。不完整度 = 两个串已经被删除的元素的数目。只有执行第二种操作后，方师傅才能从电子帐户中取出他的钱。
刚开始时，方师傅有一个空的电子账户和s的能量，请问方师傅最多可以赚多少美分？注意，由于乐警官偷吃光了方师傅的士力架，导致方师傅无法补充能量，因此方师傅的能量任何时候都不能小于0。
输入描述：
第一行4个整数，n,m,s,e(1≤n,m≤10^5;1≤s≤3×10^5;10^3≤e≤10^4)。
第二行n个整数，a1,a2⋯an.
第三行m个整数，b1,b2⋯bm.
1≤ai,bi≤10^5
输出描述：
输出一个整数，方师傅可以最多赚得的美分数目。
样例输入1：
5 5 100000 1000
1 2 3 4 5
3 2 4 5 1
样例输出1：
3
样例输入2：
3 4 3006 1000
1 2 3
1 2 4 3
样例输出2：
2
这道dp我就不说什么了，至少我是不可能做出来的，解题报告也免了，直接copy题解
首先若一定要删除一次a[i] , 假如a[i]=b[j]=b[k] j<k那么一定删除j而不是k。
用普通的dp[i][j]表示A匹配到i,B匹配到j的最大能量一定不满足(MLE&&TLE)。可以换一种思路dp[i][j]表示A匹配到了i,获得美分为j时,B上一次匹配到的最早位置。由于j不会超过300，所以可以满足条件。
转移每一次二分查找和当前a[i]匹配最近的那个b[j]值即可，可以预处理一个数组存放位置。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 100000
#define INF 0x3f3f3f3f
#define PROB "testB"
int f[][MAXN];
int n,m,e,s;
int num1[MAXN],num2[MAXN];
int ret[];
vector<int> pos[]; inline void deal(int &x,int y)
{
if (x>y)x=y;
}
int main()
{
freopen(PROB".in","r",stdin);
// freopen(PROB".out","w",stdout);
int i,j,k;
int x,y,z;
scanf("%d%d%d%d",&n,&m,&s,&e);
for (i=;i<=n;i++)
{
scanf("%d",num1+i);
}
for (i=;i<=m;i++)
{
scanf("%d",num2+i);
pos[num2[i]].push_back(i);
}
num1[]=num2[]=-;
memset(f,INF,sizeof(f));
f[][]=;
int l,r,mid;
int ans=;
for (i=;i<=n;i++)
{
f[][i]=;
for (j=;j<=;j++)
{
f[j][i]=f[j][i-];//不匹配num1[i]
r=pos[num1[i]].size();
l=-;
while (l+<r)
{
mid=(l+r)/;
if (pos[num1[i]][mid]<=f[j-][i-])
{
l=mid;
}else
{
r=mid;
}
}
if (r<pos[num1[i]].size())
deal(f[j][i],pos[num1[i]][r]);
if (ans<j&&f[j][i]+i+j*e<=s)
{
ans=j;
}
}
}
printf("%d\n",ans);
}