Fork me on GitHub

Codeforces436D

Codeforces436D题解

题意:

  • 开始有无限长的一段格子,有$n$个格子种有布丁怪兽,一开始连续的布丁怪兽算一个布丁怪兽。
  • 每回合你可以将一个布丁怪兽向左或右移动,他会在碰到第一个布丁怪兽时停下,并与其合并。
  • 如果最左边的怪兽向左,你可以认为是将其移动到了无穷远处。
  • 有$m$个特殊格子,询问最终你最多可以让几个特殊的格子上被布丁覆盖。
  • $n \leq 10000,m \leq 2000$。

题解:

  • 首先考虑两种状态:$f[i]$表示前$i$个布丁(相同的布丁怪兽算长度个)最多覆盖的特殊格子数,$g[i]$表示前$i$个布丁,第$i$个不动的情况下最多覆盖的特殊格子数,$sum(l,r)$表示$[l,r]$区间中有多少个特殊格子。那么答案就是$f[n]$。
  • 考虑如何转移:
  • 第一种:
  • 设当前转移坐标为$r=a[i]$(当前枚举到第$i$个布丁)。
  • 枚举在$r$左边的特殊格子位置$l=bj$,想要覆盖$[l,r]$区间的所有特殊格子,就至少需要另外$r-l$个布丁,即$i \geq r-l+1$,那么可以得到转移方程1:
  • 第二种:
  • 设当前转移坐标为$l=a[i]$(当前枚举到第$i$个布丁)。
  • 枚举在$l$右边的特殊格子位置$r=bj$,想要覆盖$[l,+1r]$区间的所有特殊格子,就至少需要另外$r-l$个布丁,即$i+r-l \leq n$,那么可以得到转移方程2:
  • 第三种:
  • 显然可以发现转移方程3:
  • 然后我们发现这两个数组其实可以合并,一起转移,于是就成功缩短了代码。
  • 注意到我们没有考虑一个怪兽不只是占了一格的情况,我们可以在原来转移的基础上引入$L[i],R[i]$表示第i个布丁所属的怪兽的最左边格子编号和最右边格子编号,这样就能解决上述情况。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 200009
#define M 2009
using namespace std;
int n,m,a[N],b[M],sum[N],dp[N],L[N],R[N];
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
int main()
{
n=read(),m=read();
for (int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1);
a[0]=a[1]-1000,a[n+1]=a[n]+1000;
for (int i=1;i<=n;++i)
if (a[i]==a[i-1]+1) L[i]=L[i-1];
else L[i]=i;
for (int i=n;i;--i)
if (a[i]==a[i+1]-1) R[i]=R[i+1];
else R[i]=i;
sum[0]=0;
for (int i=1;i<=m;i++) b[i]=read(),sum[b[i]]++;
sort(b+1,b+m+1);
for (int i=1;i<=200000;i++) sum[i]+=sum[i-1];
for (int i=1;i<=n;i++)
{
dp[i]=max(dp[i],dp[i-1]);
int Max;
if (L[i]==i) Max=dp[i-1]+sum[a[i]]-sum[a[i]-1];
else Max=-10000000;
dp[i]=max(dp[i],Max);
for (int l=1;b[l]<=a[i]&&l<=m;l++)
if (i-(a[i]-b[l])>=1)
{
dp[i]=max(dp[i],dp[L[i-(a[i]-b[l])]-1]+sum[a[i]]-sum[b[l]-1]);
Max=max(Max,dp[L[i-(a[i]-b[l])]-1]+sum[a[i]]-sum[b[l]-1]);
}
for (int r=m;b[r]>=a[i]&&r;r--)
if (i+b[r]-a[i]<=n)
dp[R[i+b[r]-a[i]]]=max(dp[R[i+b[r]-a[i]]],Max+sum[b[r]]-sum[a[i]]);
}
printf("%d\n",dp[n]);
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces436D

文章作者:wzf2000

发布时间:2017年12月23日 - 22:12

最后更新:2017年12月25日 - 11:12

原始链接:https://wzf2000.github.io/2017/12/23/Codeforces436D/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。