神级dp（反正不是我能想到的思路）
要求活动都是时间岔开，所以两个会场选择的活动可以分成是一段一段的区间。
不妨让A选择中间连续的一段区间，B会场选择的是两段剩下的活动。
时间大但n小，所以可以先离散化。
num[l][r]表示时间[l，r]的区间内，完整的活动个数。
活动时间不计开始和结束时间，为了方便处理，我们可以把s计入活动中，把t减一，然后每个活动的时间就不能有交点。
我们先定义pre[i][j]为从时间1到i（这里的时间都是离散化了的），在一个会场选择j个活动，另一个会场可选的最大活动数。
那么pre的转移为：
for(int i=1;i<=tot;++i) for(int j=0;j<=num[1][i];++j) { if(j==0)pre[i][j]=num[1][i]; for(int k=0;k<=i;++k) { if(num[1][k]>=j) pre[i][j]=max(pre[i][j],pre[k][j]+num[k+1][i]); if(j>=num[k+1][i])pre[i][j]=max(pre[i][j],pre[k][j-num[k+1][i]]); //枚举断点k //在1~i内选择j个，可在1~k内选择j个，剩下k+1到i里的全分给另一个会场 //或者把k+1~i内的活动全部选完，把1~k里多的分给另一个会场 } }
定义nextt[i][j]为从时间i到tot（tot是最大的时间），在一个会场选择j个活动，另一个会场可选的最大活动数。
转移与nextt类似：
for(int i=tot;i>=1;--i) for(int j=0;j<=num[i][tot];++j) { if(j==0)nextt[i][j]=num[i][tot]; for(int k=tot+1;k>=i;--k) { if(num[k][tot]>=j) nextt[i][j]=max(nextt[i][j],nextt[k][j]+num[i][k-1]); if(j>=num[i][k-1])nextt[i][j]=max(nextt[i][j],nextt[k][j-num[i][k-1]]); } }
如果没有必须选某一个活动的限制，用pre就可以求出答案：
int ans=-1; for(int i=0;i<=n;++i) ans=max(ans,min(i,pre[tot][i])); printf("%d\n",ans);
如果有限制，我们设f[i][j]为从时间i到j这一段必须选求得的答案。
不妨让A会场选中这一段，那么它还可以在这段时间的前后再选几个活动，剩下的就是B会场的。
那么每一次都要枚举x，y，i，j，时间为O（n^4）。
这里有一个单调性优化：
我们可以感性理解一下（因为我不会证）：
当A会场在x多选了几个，对应的y就要少选，毕竟求的是两个会场的较小值。
for(int len=tot;len;len--) for(int l=1;l+len-1<=tot;l++) { int r=l+len-1,y=num[r+1][tot]; f[l][r]=max(f[l-1][r],f[l][r+1]);//!!! for(int x=0; x<=num[1][l-1]; x++) { while(y>0&&cal(l,r,x,y-1)>=cal(l,r,x,y))y--;//单调性优化 f[l][r]=max(f[l][r],cal(l,r,x,y)); } }
然后贴出完整代码~
#include<bits/stdc++.h> #define N 403//注意范围，每个活动存了始终两个时间 #define LL long long #define INF 10000 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } struct act{ int s,t,ord,res; }w[402]; int b[N],f[2*N][N],pre[2*N][N],nextt[2*N][N],num[2*N][N],g[2*N][N],F[2*N][N]; int tot=0,n; void init() { sort(b+1,b+1+tot); for(int i=1;i<=n;++i) { w[i].s=lower_bound(b+1,b+1+tot,w[i].s)-b; w[i].t=lower_bound(b+1,b+1+tot,w[i].t)-b; for(int l=w[i].s;l;--l) for(int r=w[i].t;r<=tot;++r) num[l][r]++; } for(int i=0;i<=tot;++i) for(int j=1;j<=n;++j)//前i个时间A选择j个活动后B最多多少个活动，后i个时间A选择j个活动后B最多多少个活动 pre[i][j]=-INF,nextt[i][j]=-INF; } int cal(int l,int r,int x,int y) { return min(x+y+num[l][r],pre[l-1][x]+nextt[r+1][y]); } void work() { for(int i=1;i<=tot;++i) for(int j=0;j<=num[1][i];++j) { if(j==0)pre[i][j]=num[1][i]; for(int k=0;k<=i;++k) { if(num[1][k]>=j) pre[i][j]=max(pre[i][j],pre[k][j]+num[k+1][i]); if(j>=num[k+1][i])pre[i][j]=max(pre[i][j],pre[k][j-num[k+1][i]]); //枚举断点k //在1~i内选择j个，可在1~k内选择j个，剩下k+1到i里的全分给另一个会场 //或者把k+1~i内的活动全部选完，把1~k里多的分给另一个会场 } } for(int i=tot;i>=1;--i) for(int j=0;j<=num[i][tot];++j) { if(j==0)nextt[i][j]=num[i][tot]; for(int k=tot+1;k>=i;--k) { if(num[k][tot]>=j) nextt[i][j]=max(nextt[i][j],nextt[k][j]+num[i][k-1]); if(j>=num[i][k-1])nextt[i][j]=max(nextt[i][j],nextt[k][j-num[i][k-1]]); } } int ans=-1; for(int i=0;i<=n;++i) ans=max(ans,min(i,pre[tot][i])); printf("%d\n",ans); for(int len=tot;len;len--) for(int l=1;l+len-1<=tot;l++) { int r=l+len-1,y=num[r+1][tot]; f[l][r]=max(f[l-1][r],f[l][r+1]);//!!! for(int x=0; x<=num[1][l-1]; x++) { while(y>0&&cal(l,r,x,y-1)>=cal(l,r,x,y))y--;//单调性优化 f[l][r]=max(f[l][r],cal(l,r,x,y)); } } for(int i=1;i<=n;++i) printf("%d\n",f[w[i].s][w[i].t]); } int main() { freopen("show.in","r",stdin); freopen("show.out","w",stdout); n=read(); for(int i=1;i<=n;++i) { w[i].s=read(); int t=read(); w[i].t=w[i].s+t-1; b[++tot]=w[i].s; b[++tot]=w[i].t; } init(); work(); }
所以说这是什么神仙dp啊
原文：https://www.cnblogs.com/yyys-/p/11514692.html
