题面
题目描述
输入
输出
样例输入
10 5 110 3 100 200 150 140 129 134 167 198 200 111 0 30 20 40 90 100 100 110 50 60
样例输出
7
数据范围
题解
这题很水，可以把苹果看成一个高度数轴上的点，板凳看成线段，这样就变成了一道经典的直线上有一些点，有n条线段，能用k条，使覆盖点数最多的问题。直接一个二维DP设 f[i][j]表示 选到第i条板凳（第i个默认必选）（板凳要按双关键字排序，分别为head和tail，都是从小到大），已选j条板凳时收获的最多苹果，枚举k从1~i-1表示从哪条线段转移。 不难发现，转移只有3种情况：
1：
如图所示，显然，tail[k]在head[i]之后，所以能起到作用的只有tail[k]，这里我们用一个***前缀和***(h数组)来维护苹果在某一高度及以下的数量（这里要减去身高），所以f[i][j]=max(f[i][j],f[k][j-1]+h[tail[i]]-h[tail[k]])。
大家都知道，为了算前缀和，head的位置应该减一，但这里的tail[k]这个位置已经被取过了，所以当前线段能产生的贡献只有tail[k]+1~tail[i]，即为上面的式子。
2：
即如上显示的完全不相交的两条线段，转移为f[i][j]=max(f[i][j],f[k][j-1]+h[tail[i]]-h[head[i]-1])。
3：
如上所示，第i条线段不会产生任何贡献，所以直接f[i][j]=max(f[i][j],f[k][j-1])。
正确性
有些人可能会问若碰到以下这种情况，你的答案会不会出错，即第i条线段从第j条线段转移而来，第j条从第k条转移而来。
但程序的统计是这样的
所以算法是正确的。
代码
#include<bits/stdc++.h>
using namespace std
;
int i
,j
,n
,m
,k
,l
,o
,p
,h
[2000005],f
[205][205];
struct node
{
int a
,b
;
};
node d
[205];
int cmp(node x
,node y
)
{
return x
.a
<y
.a
||(x
.a
==y
.a
&&x
.b
<y
.b
);
}
int main()
{
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
scanf("%d %d %d %d",&n
,&m
,&o
,&p
);
for (i
=1;i
<=n
;i
++)
{
scanf("%d",&l
);
h
[(l
-o
+2000000+1)%2000000]++;
}
for (i
=1;i
<=2000000;i
++)
{
h
[i
]=h
[i
]+h
[i
-1];
}
for (i
=1;i
<=m
;i
++)
{
scanf("%d %d",&d
[i
].a
,&d
[i
].b
);
d
[i
].a
++;
d
[i
].b
++;
}
sort(d
+1,d
+m
+1,cmp
);
int ans
=0;
for (i
=1;i
<=m
;i
++)
{
f
[i
][1]=h
[d
[i
].b
]-h
[d
[i
].a
-1];
for (j
=i
-1;j
>=1;j
--)
{
if (d
[j
].b
<d
[i
].b
)
for (k
=2;k
<=p
;k
++)
{
f
[i
][k
]=max(f
[i
][k
],f
[j
][k
-1]+h
[d
[i
].b
]-h
[max(d
[i
].a
,d
[j
].b
+1)-1]);
ans
=max(ans
,f
[i
][k
]);
}
}
}
printf("%d",ans
);
}
码风有点丑，请见谅。
