【DP/WQS二分】Codeforces 958E2 Guard Duty (medium)

题面在这里

把时间间隔看作元素，间隔长度看作代价

问题就转化为：N个元素取K个不相邻元素，使代价最小

两种解法：

一、WQS二分

可以先WQS二分去掉一维K

即每个元素的代价加上\(mid\)，不限制取的个数

用DP验证最优决策下取的个数是否超过K即可

时间复杂度\(O(NlogN)\)

二、直接DP

\(f_{i,j,0/1}\)表示前i个取了j个，第i个是否取 的最小代价

这样复杂度是\(O(NK)\)的

但是可以发现最优解一定只需要前\(3K\)小的元素

这样把前\(3K\)个元素拿来DP，复杂度就是\(O(N^2)\)

示例程序1：

#include<cstdio>
#include<cstring> 
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;

const int maxn=500005;
const double eps=1e-3; 
int n,K,a[maxn],g[maxn];
double f[maxn];
void check(double w){
	f[0]=0;f[1]=min(a[1]+w,0.0);
	for (int i=2;i<=n;i++)
	 if (f[i-1]>f[i-2]+a[i]+w)
	  f[i]=f[i-2]+a[i]+w,g[i]=g[i-2]+1;else
	  f[i]=f[i-1],g[i]=g[i-1];
}
int main(){
	scanf("%d%d",&K,&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for (int i=1;i<n;i++) a[i]=a[i+1]-a[i];n--;
	double l=-1e9,r=1e9,mid;
	while (r-l>eps){
		mid=(l+r)/2;
		if (check(mid),g[n]<K) r=mid;else l=mid;
	}
	check(mid=(l+r)/2);
	printf("%.0lf",f[n]-K*mid);
	return 0;
}

示例程序2：

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=500005;
struct note{
	int w,wz;
	bool operator < (const note lyf) const {return w<lyf.w;}
}q[N];
int k,n,a[N],d[N],b[N],f[4][N],p;

inline char nc(void){
	static char ch[100010],*p1=ch,*p2=ch;
	return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++;
}

inline void read(int &a){
	static char c=nc();int f=1;
	for (;!isdigit(c);c=nc()) if (c=='-') f=-1;
	for (a=0;isdigit(c);a=(a<<3)+(a<<1)+c-'0',c=nc());
	return (void)(a*=f);
}

int main(){
	read(k),read(n);
	for (int i=1; i<=n; ++i) read(a[i]);
	sort(a+1,a+1+n);
	for (int i=1; i<n; ++i) d[i]=q[i].w=a[i+1]-a[i],q[i].wz=i;
	sort(q+1,q+n);
	for (int i=1; i<=min(n,3*k); ++i) b[q[i].wz]=1;
	memset(f,0x3f,sizeof f);
	for (int i=0; i<=3; ++i) f[i][0]=0;
	for (int i=1; i<=n; ++i)
		if (b[i]){
			++p;
			for (int j=1; j<=min(p,k); ++j)
				f[p&3][j]=min(f[(p-1)&3][j],f[(p-1-b[i-1])&3][j-1]+d[i]);
		}
	return printf("%d\n",f[p&3][k]),0;
}