陶陶摘苹果

题目

Description

Input

Output

Sample Input

10 5 110 3

100 200 150 140 129 134 167 198 200 111

0 30

20 40

90 100

100 110

50 60

Sample Output

Data Constraint

题解

题目大意

一条线上有\(n\)个点，有\(m\)条线段，最多选\(k\)条线段使得覆盖的点最多

分析

考虑\(DP\)

设\(f[i][j]\)表示到了第\(i\)条线段，已经选了\(j\)条，当前这个必选的最多点数

转移

枚举一个\(k\)表示上一条线段

\(f[i][j]=max(f[k][j-1]+新的点数)\)

新的点数可以用前缀和维护

总结

没有想出DP式子

在设状态的时候可以想想要求什么，什么是变量

然后用变量来设状态

Code

#include<bits/stdc++.h>

using namespace std;

struct node

{

	int begin,end;

}c[205];

int n,m,h,k,x,mx,ans,a[1000005],f[205][205];

int read()

{

	int res=0;char ch=getchar();

	while (ch<'0'||ch>'9') ch=getchar();

	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();

	return res;

}

bool cmp(node x,node y)

{

	return x.end<y.end;

}

int main()

{

	freopen("apple.in","r",stdin);

	freopen("apple.out","w",stdout);

	n=read();m=read();h=read();k=read();

	for (int i=1;i<=n;++i)

	{

		x=read();x-=h;

		if (x<0) continue;

		++a[x];

	}

	for (int i=1;i<=1000000;++i)

		a[i]+=a[i-1];

	for (int i=1;i<=m;++i)

		c[i].begin=read(),c[i].end=read();

	sort(c+1,c+1+m,cmp);

	f[1][1]=a[c[1].end]-a[max(0,c[1].begin-1)];

	ans=f[1][1];

	for (int i=2;i<=m;++i)

	{

		f[i][1]=a[c[i].end]-a[max(0,c[i].begin-1)];

		ans=max(ans,f[i][1]);

		for (int j=2;j<=min(i,k);++j)

		{

			for (int k=1;k<i;++k)

				f[i][j]=max(f[i][j],f[k][j-1]+a[c[i].end]-a[max(c[k].end+1,c[i].begin)-1]);

			ans=max(ans,f[i][j]);

		}

	}

	printf("%d\n",ans);

	fclose(stdin);

	fclose(stdout);

	return 0;

}

巴特西

JZOJ 2020.10.6 【NOIP2017提高A组模拟9.7】陶陶摘苹果