codeforces 425C Sereja and Two Sequences（DP）

题意读了好久才读懂。。。。不知道怎么翻译好~~请自便~~~

http://codeforces.com/problemset/problem/425/C

看懂之后纠结好久。。。不会做。。。仍然是看题解看代码才懂的。。。

dp[i][j]表示A数组前i个数，第一个操作做j次的B数组的最小下标。代码里把第一维给压掉了。

复杂度，n*s/e*logn吧。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std;

#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-8
#define maxn 100010

int a[maxn],b[maxn];
int dp[333];
vector<int>x[maxn];
int main(){
    int n,m,s,e;
    while(~scanf("%d%d%d%d",&n,&m,&s,&e)){
        memset(dp,0x3f,sizeof(dp));
        dp[0]=0;
        for(int i=0;i<n;++i)scanf("%d",a+i);
        //for(int i=0;i<maxn;++i)x[i].clear();
        for(int i=0;i<m;++i)scanf("%d",b+i),x[b[i]].push_back(i+1);
        int ans=0;
        for(int i=0;i<n;++i){
            for(int j=s/e;j>=0;--j){
                vector<int>::iterator it=upper_bound(x[a[i]].begin(),x[a[i]].end(),dp[j]);
                if(it==x[a[i]].end())continue;
                dp[j+1]=min(*it,dp[j+1]);
                if(i+1+dp[j+1]+(j+1)*e<=s)
                    ans = max(ans,j+1);
            }
        }
        printf("%d
",ans);
    }
    return 0;
}