题目
分析：
拿到题，注意到数据范围很小，又是求最大值，可以往dp那方面想一下。
难点在于，如何使AB会场的分配尽量均匀，且活动多。考虑固定A选的活动数，去求B选的最多活动数。为了使时间不交叉，将时间压成一维。
预处理每一个区间中对应的活动数sum[ i ][ j ]。
定义：dp[ i ][ j ]表示1~i 的时间中，A会场选j个，B会场最多选的个数。
转移：为了保证不交叉，模拟区间转移的方法：枚举断点k，大区间由小区间转移过来。
1.dp[ k ][ j ]+sum[ k ][ i ];
A会场只在1~k的时间里选j个，后面的全部留给B，前面的也留一些给B。
2.dp[ k ][ j-sum[ k ][ i ] ]；
A会场从前面选 j-sum[ k ][ i ] 个，再从后面选 sum[ k ][ i ] 。
这样就可以不重不漏地考虑完所有情况了。
题目中还要求强制性选择，就加一个ansss[ l ][ r ]数组，表示强制选择l~r区间的最大值，转移见代码。
#include<bits/stdc++.h> using namespace std; #define ri register int #define N 405 int n,l[N],r[N],tmp[N],u[N],v[N],ls[N],pre[N][N],aft[N][N],sum[N][N],anss[N]; int main() { freopen("show.in","r",stdin); freopen("show.out","w",stdout); int cnt=0,t; scanf("%d",&n); for(ri i=1;i<=n;++i){ scanf("%d%d",&l[i],&r[i]); r[i]+=l[i]; tmp[++cnt]=l[i],tmp[++cnt]=r[i]; } sort(tmp+1,tmp+1+cnt); ls[1]=1;//！！！保证从1开始 因为后面的时间点都是从1开始枚举的 for(ri i=2;i<=cnt;++i) if(tmp[i]!=tmp[i-1]) ls[i]=ls[i-1]+1;//离散化 else ls[i]=ls[i-1]; for(ri i=1;i<=n;++i) for(ri j=1;j<=cnt;++j){ if(l[i]==tmp[j]) u[i]=ls[j]; if(r[i]==tmp[j]) v[i]=ls[j]; } t=ls[cnt]; for(ri i=1;i<=t;++i) for(ri j=i;j<=t;++j) for(ri k=1;k<=n;++k){ if(u[k]>=i && v[k]<=j) sum[i][j]++; } int inf=1000; for(ri i=1;i<=t;++i) for(ri j=1;j<=n;++j) pre[i][j]=aft[i][j]=-inf; for(ri i=1;i<=t;++i) for(ri j=0;j<=sum[1][i];++j){ if(j==0) { pre[i][j]=sum[1][i]; continue; } //先初始化 令前i的时间选0个给A会场 = 把前i时间的所有都给B会场 for(ri k=1;k<=i;++k){ pre[i][j]=max(pre[i][j],pre[k][j]+sum[k][i]);//从前k的时间选j个给A会场 后k~i的时间都给B会场 if(j>=sum[k][i]) pre[i][j]=max(pre[i][j],pre[k][j-sum[k][i]]); //从前k的时间选j-sum[k][i]个给A会场 后面再选sum[k][i]个给A会场 就凑齐了j个给A会场 } } //反着再求一次aft 表示从i~t A会场选j个，B会场选的个数 for(ri i=t;i>=1;--i) for(ri j=0;j<=sum[i][t];++j){ if(j==0) { aft[i][j]=sum[i][t]; continue; } for(ri k=t;k>=i;--k){//从后往前枚举断点 类区间dp的更新 aft[i][j]=max(aft[i][j],aft[k][j]+sum[i][k]); if(j>=sum[i][k]) aft[i][j]=max(aft[i][j],aft[k][j-sum[i][k]]); } } int ans=0; for(ri i=1;i<=n;++i) ans=max(ans,min(i,pre[t][i])); printf("%d ",ans); //ans[l][r]表示强制选l到r这段区间的最大数 for(ri k=1;k<=n;++k) for(ri i=u[k];i>=1;--i)//将左端点向左延伸 for(ri j=v[k];j<=t;++j){//右端点向右延伸 for(ri l=0;l<=sum[1][i];++l){//让A在左边选l个 for(ri r=0;r<=sum[j][t];++r){//让A在右边选r个 //中间的全部分给A anss[k]=max(anss[k],min( sum[i][j]+l+r , pre[i][l]+aft[j][r] )); if(aft[j][r]<r) break;//r在增加时 aft[j][r]是单调递减的 //这个剪枝的意思是：右边选的太少了 B会场相应的也会很少 答案就不会再被更新了 } if(pre[i][l]<l) break;//同上 } if(sum[i][j]>sum[1][i]+sum[j][t]) break;//A选得太多了 会导致A、B不平衡 答案也无法被更新 相当于一个剪枝 if(anss[k]>sum[1][i]+sum[j][t]) break;//左右全部都分给B都更新不了答案 再枚举也没有意义了 } for(ri i=1;i<=n;++i) printf("%d ",anss[i]); } /* 10 15 6 13 12 20 17 1 18 5 14 18 9 15 25 21 16 16 9 19 14 5 8 2 1 5 5 3 3 2 5 3 */