Contest20140705 testB DP

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题解

 

1. 首先若一定要删除一次a[i] , 假如a[i]=b[j]=b[k] j<k那么一定删除j而不是k。

2. 用普通的dp[i][j]表示A匹配到i,B匹配到j的最大能量一定不满足(MLE&&TLE)。可以换一种思路dp[i][j]表示A匹配到了i,获得美分为j时,B上一次匹配到的最早位置。由于j不会超过300，所以可以满足条件。

3. 转移每一次二分查找和当前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[310][MAXN];
int n,m,e,s;
int num1[MAXN],num2[MAXN];
int ret[100010];
vector<int> pos[100010];

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=1;i<=n;i++)
        {
                scanf("%d",num1+i);
        }
        for (i=1;i<=m;i++)
        {
                scanf("%d",num2+i);
                pos[num2[i]].push_back(i);
        }
        num1[0]=num2[0]=-1;
        memset(f,INF,sizeof(f));
        f[0][0]=0;
        int l,r,mid;
        int ans=0;
        for (i=1;i<=n;i++)
        {
                f[0][i]=0;
                for (j=1;j<=300;j++)
                {
                        f[j][i]=f[j][i-1];//不匹配num1[i]
                        r=pos[num1[i]].size();
                        l=-1;
                        while (l+1<r)
                        {
                                mid=(l+r)/2;
                                if (pos[num1[i]][mid]<=f[j-1][i-1])
                                {
                                        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
",ans);
}