CodeForces 425C Sereja and Two Sequences

本文主要是介绍CodeForces 425C Sereja and Two Sequences，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

两组数字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]后的第一个相同的数字匹配 （可以这么做的原因是  保证第二种操作的花费最小  同时留下尽量多的数字供后面使用）

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100010
#define inf (1U<<31)-1int n,m,s,e,ans;
int a[N],b[N],dp[305][N];
vector<int> ed[N];int main()
{int i,j,k;scanf("%d%d%d%d",&n,&m,&s,&e);for(i=1;i<=n;i++) scanf("%d",&a[i]);for(j=1;j<=m;j++){scanf("%d",&b[j]);ed[b[j]].push_back(j);}for(i=0;i<N;i++) ed[i].push_back(inf);memset(dp,-1,sizeof(dp));memset(dp[0],0,sizeof(dp[0]));for(i=1;i<=s/e;i++){for(j=1;j<=n;j++){if(dp[i-1][j-1]!=-1){dp[i][j]=dp[i][j-1];k=lower_bound(ed[a[j]].begin(),ed[a[j]].end(),dp[i-1][j-1]+1)-ed[a[j]].begin();k=ed[a[j]][k];if(k==inf) continue;if(dp[i][j]==-1||dp[i][j]>k) dp[i][j]=k;if(dp[i][j]+j+i*e<=s) ans=max(ans,i);}}}printf("%d\n",ans);return 0;
} 

这篇关于CodeForces 425C Sereja and Two Sequences的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---