题解:
我们设计状态方程如下:
num[i][j]表示从时间i到j中有多少个
pre[i][j]表示时间1~i中,A选了j个时的B能选的数量的最大值.
nex[i][j]表示时间i~cnt中,A选了j个时的B能选的数量的最大值.
mus[i][j]表示从时间i到j的保证选时,A和B选的数量中的较小值的最大值.
①对于num数组直接可以暴力求,没问题.
②对于pre和nex数组在这里就只讲pre的转移,nex的转移类似.
pre[i][j]=max(pre[i-1][j],pre[k][j]+num[k][i],pre[k][j-num[k][i]]);(1<=k
③对于mus数组,我们得到转移方程mus[i][j]=max(min(x+y,pre[i][x]+num[i][j]+nex[j][y])),x表示时间1~i中A选x个,y表示时间j~cnt中A选y个,中间num[i][j]个由B选.这样暴力转移的话是O(n^4)的,时间上是不允许的,那么我们观察转移方程,当x增大时,y只有单调递减答案才会更优,因为如果x增大且y也增大的话,表示A选的越来越多,B选的越来越少,显然答案不会更优的,所以我们维护一个y的单调递减的指针来转移就可以了,时间O(n^3).
④对于第一问的答案就是max(min(pre[i][j],j)),枚举时间i和A选的个数j来得到最优解.
然后对于第二问我们对于一个活动l~r,答案为max(mus[i][j]),1<=i<=l,r<=j<=cnt.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define MAXN 10100
#define RG register
#define LL long long int
using namespace std;
const int INF=1e9;
struct node{int l,r;int id;
}t[1010];
int n;
int num[1010][1010];//从时间i到j中有多少个
int pre[1010][1010];//时间1~i中,A选了j个时的B能选的数量的最大值.
int nex[1010][1010];//时间i~n中,A选了j个时的B能选的数量的最大值.
int mus[1010][1010];//从时间i到j的保证选时,A和B选的数量中的较小值的最大值.
int st[MAXN],cnt;
int ans[MAXN];
int main()
{freopen("1.in","r",stdin);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&t[i].l,&t[i].r);t[i].r+=t[i].l;t[i].id=i;st[++cnt]=t[i].l;st[++cnt]=t[i].r;}sort(st+1,st+cnt+1);cnt=unique(st+1,st+cnt+1)-st-1;for(int i=1;i<=n;i++){t[i].l=lower_bound(st+1,st+cnt+1,t[i].l)-st;t[i].r=lower_bound(st+1,st+cnt+1,t[i].r)-st;}for(int i=1;i<=cnt;i++)for(int j=1;j<=t[i].l;j++)for(int k=t[i].r;k<=cnt;k++)num[j][k]++;for(int i=1;i<=cnt;i++)for(int j=1;j<=n;j++)pre[i][j]=nex[i][j]=-INF;pre[0][0]=nex[cnt+1][0]=0;for(int i=1;i<=cnt;i++){for(int j=0;j<=num[1][i];j++)pre[i][j]=max(pre[i-1][j],pre[i][j]);for(int j=0;j<=num[1][i];j++){for(int k=1;k=num[k][i]) pre[i][j]=max(pre[k][j-num[k][i]],pre[i][j]);}}}for(int i=cnt;i>=1;i--){for(int j=0;j<=num[i][cnt];j++)nex[i][j]=max(nex[i+1][j],nex[i][j]);for(int j=0;j<=num[i][cnt];j++){for(int k=cnt;k>i;k--){nex[i][j]=max(nex[k][j]+num[i][k],nex[i][j]);if(j>=num[i][k]) nex[i][j]=max(nex[k][j-num[i][k]],nex[i][j]);}}}for(int i=1;i<=cnt;i++)for(int j=i+1;j<=cnt;j++){for(int x=0,y=n;x<=n;x++){while(y){int val1=min(x+y,pre[i][x]+num[i][j]+nex[j][y]);int val2=min(x+y-1,pre[i][x]+num[i][j]+nex[j][y-1]);if(val2>=val1) y--;else break;}mus[i][j]=max(mus[i][j],min(x+y,pre[i][x]+num[i][j]+nex[j][y]));}}for(int i=1;i<=cnt;i++)for(int j=0;j<=num[1][i];j++)ans[0]=max(ans[0],min(pre[i][j],j));for(int i=1;i<=n;i++)for(int j=t[i].l;j>=1;j--)for(int k=t[i].r;k<=cnt;k++)ans[i]=max(ans[i],mus[j][k]);for(int i=0;i<=n;i++) printf("%d
",ans[i]);return 0;
}