description

大神 wyp 开了家工厂，工厂有 n 个工人和 p 条流水线。

工厂的工人都是睡神，因此第 i 个工人只会在 si 至 ti 时刻才会工作。

每个工人都会被分派到一条流水线上，然而，一条流水线只会在这条线的工人到齐

时才能开工，其余时间即使有部分工人到了也只能休息。

根据大神 wyp 的神谕，不能有流水线的工作时间为 0，也不能有工人没被分派到

流水线上（即使这样会降低实际工作时间）。

工人们 dp 不过关，所以请你求出能得到的最大的工作时间总和。

保. 证. 题. 目. 至. 少. 存. 在. 一. 种. 合. 法. 的. 分. 配. 方. 案。.

阅读样例以更好地理解本题。

analysis

首先把区间分成两种，不包含任何区间的区间为\(A\)集合，包含至少一个区间的区间为\(B\)集合
那么明显把\(B\)里的区间和\(A\)放到一组答案肯定不会更优，于是考虑\(B\)里的区间都单独分组
按左端点排序后对\(A\)进行\(DP\)，设\(f[i][j]\)表示选前\(i\)个区间分了\(j\)组的最大答案
\(f[j][k+1]=max(f[i][k]+t[j+1]-s[j])\ (s[j]<t[j+1])\)，\(O(n^3)\)转移
转移的限制条件保证了两个区间有交
最后枚举一下有几个区间由\(A\)的区间组成，剩下的区间就取\(B\)最长的几个区间单独分组

code

#pragma GCC optimize("O3")

#pragma G++ optimize("O3")

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define MAXN 205

#define ha 19260817

#define ll long long

#define reg register ll

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll f[MAXN][MAXN];

bool bz[MAXN];

ll pre[MAXN];

ll n,m,p,tmp,ans=-ha;

struct node

{

	ll x,y;

}a[MAXN],A[MAXN],B[MAXN];

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

inline ll max(ll x,ll y){return x>y?x:y;}

inline bool cmp(node a,node b){return a.y-a.x>b.y-b.x;}

inline bool cmpp(node a,node b){return a.x<b.x;}

int main()

{

	//freopen("T2.in","r",stdin);

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

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

	n=read(),p=read(),memset(bz,1,sizeof(bz));

	fo(i,1,n)a[i].x=read(),a[i].y=read();

	fo(i,1,n)fo(j,1,n)if (i!=j)

	if ((a[i].x<a[j].x && a[j].y<=a[i].y) || (a[i].x<=a[j].x && a[j].y<a[i].y)){B[++tmp]=a[i],bz[i]=0;break;}

	fo(i,1,n)if (bz[i])A[++m]=a[i];

	sort(A+1,A+m+1,cmpp);

	memset(f,128,sizeof(f)),f[0][0]=0;

	fo(i,0,m-1)fo(k,0,p-1)fo(j,i+1,m)if (A[j].x<A[i+1].y)f[j][k+1]=max(f[j][k+1],f[i][k]+A[i+1].y-A[j].x);

	sort(B+1,B+n-m+1,cmp);

	fo(i,1,n-m)pre[i]=pre[i-1]+B[i].y-B[i].x;

	fo(i,1,p)ans=max(ans,f[m][i]+pre[p-i]);

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

	return 0;

}

巴特西

【JZOJ6367】工厂(factory)

description

analysis

code

最新文章

热门文章