NOI2011 在吉林大学开始啦！为了迎接来自全国各地最优秀的信息学选手， 吉林大学决定举办两场盛大的 NOI 嘉年华活动，分在两个不同的地点举办。每 个嘉年华可能包含很多个活动，而每个活动只能在一个嘉年华中举办。 现在嘉年华活动的组织者小安一共收到了 n个活动的举办申请，其中第 i 个 活动的起始时间为 Si，活动的持续时间为Ti。这些活动都可以安排到任意一个嘉 年华的会场，也可以不安排。 小安通过广泛的调查发现，如果某个时刻，两个嘉年华会场同时有活动在进 行（不包括活动的开始瞬间和结束瞬间），那么有的选手就会纠结于到底去哪个 会场，从而变得不开心。所以，为了避免这样不开心的事情发生，小安要求不能 有两个活动在两个会场同时进行（同一会场内的活动可以任意进行）。 另外，可以想象，如果某一个嘉年华会场的活动太少，那么这个嘉年华的吸 引力就会不足，容易导致场面冷清。所以小安希望通过合理的安排，使得活动相 对较少的嘉年华的活动数量最大。 此外，有一些活动非常有意义，小安希望能举办，他希望知道，如果第i 个 活动必须举办（可以安排在两场嘉年华中的任何一个），活动相对较少的嘉年华 的活动数量的最大值。
输入的第一行包含一个整数 n，表示申请的活动个数。 接下来 n 行描述所有活动，其中第 i 行包含两个整数 Si、Ti，表示第 i 个活 动从时刻Si开始，持续 Ti的时间。
输出的第一行包含一个整数，表示在没有任何限制的情况下，活动较少的嘉 年华的活动数的最大值。 接下来 n 行每行一个整数，其中第 i 行的整数表示在必须选择第 i 个活动的 前提下，活动较少的嘉年华的活动数的最大值。
在没有任何限制的情况下，最优安排可以在一个嘉年华安排活动 1, 4，而在 另一个嘉年华安排活动 3, 5，活动2不安排。
1≤n≤200 0≤Si≤10^9 1≤Ti≤ 10^9
Day2
[ Submit][ Status][ Discuss]题解：dp
第一问 先将区间离散，时间就全是O(n)级别的了。 预处理sum[i][j]表示i到j时间有多少个活动。 设f[i][j]表示到第i时间为止，第一个场地已经举办了j场活动时第二个场地最多举办多少场活动。 f[i][j]=max{f[i-1][j],f[k][j]+sum[k+1][i],f[k][j-sum[k+1][i]]} 分别表示sum[k+1][i]这一段的活动不演出，在第二个场地演出，在第一个场地演出。 复杂度O(n^3)
再用同样的方法求g[i][j]表示倒序时间到i时，第一个场地举办了j个活动时第二个场地最多举办多少个活动。 设dp[i][j]表示i~j这一段所有的活动同时选到某一个场地的最大答案。
dp[i][j]=max(dp[i][j],min(max(f[i-1][x]+g[j+1][y],x+y),min(f[i-1][x]+g[j+1][y],x+y)+sum[i][j]) 表示把sum[i][j]这一段给一二场地中较小的一个场地，再更新答案。
这样直接暴力O(N^4)
但是随着x的增加y 是单调不降的，所以最终的时间复杂度是O(N^3)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 1003 using namespace std; int n,m,x[N],b[N],pos[N],l[N],r[N],cnt,inf; int f[N][N],sum[N][N],g[N][N],dp[N][N],ans1[N]; struct data { int x,pd,num,k; }a[N]; int cmp(data x,data y) { return x.x<y.x; } void solve() { for (int i=1;i<=cnt;i++) for (int j=i;j<=cnt;j++) for (int k=1;k<=n;k++) if (l[k]>=i&&r[k]<=j) sum[i][j]++; } void calc_f() { memset(f,128,sizeof(f)); f[0][0]=0; for (int i=1;i<=cnt;i++) for (int j=0;j<=n;j++) { f[i][j]=f[i-1][j]; for (int k=0;k<=i-1;k++) { f[i][j]=max(f[i][j],f[k][j]+sum[k+1][i]); if (j-sum[k+1][i]>=0) f[i][j]=max(f[i][j],f[k][j-sum[k+1][i]]); } } } void calc_g() { memset(g,128,sizeof(g)); inf=g[0][0]; g[cnt+1][0]=0; for (int i=cnt;i>=1;i--) for (int j=0;j<=n;j++) { g[i][j]=g[i+1][j]; for (int k=cnt+1;k>i;k--) { g[i][j]=max(g[i][j],g[k][j]+sum[i][k-1]); if (j-sum[i][k-1]>=0) g[i][j]=max(g[i][j],g[k][j-sum[i][k-1]]); } } } int calc(int i,int j,int x,int y) { if (f[i-1][x]<0||g[j+1][y]<0) return inf; int t=max(x+y,f[i-1][x]+g[j+1][y]); int t1=min(x+y,f[i-1][x]+g[j+1][y]); return min(t,t1+sum[i][j]); } int main() { scanf("%d",&n); int size=0; for (int i=1;i<=n;i++) { int s,t; scanf("%d%d",&s,&t); ++size; a[size].pd=1; a[size].x=s; a[size].num=i; ++size; a[size].pd=0; a[size].x=s+t-1; a[size].num=i; } sort(a+1,a+2*n+1,cmp); cnt=0; a[0].x=-1; for (int i=1;i<=2*n;i++) if (a[i].x!=a[i-1].x) cnt++,a[i].k=cnt; else a[i].k=cnt; for (int i=1;i<=2*n;i++) { if (a[i].pd) l[a[i].num]=a[i].k; else r[a[i].num]=a[i].k; } solve(); calc_f(); calc_g(); for (int i=1;i<=cnt;i++) for (int j=i;j<=cnt;j++) if (sum[i][j]) { int y=n,t; for (int x=0;x<=n;x++) { int now=calc(i,j,x,y); while(y) { int nxt=calc(i,j,x,y-1); if (now<=nxt) now=nxt,y--; else break; } dp[i][j]=max(dp[i][j],now); } } int ans=0; for (int i=1;i<=n;i++) ans=max(ans,min(g[1][i],i)); for (int k=1;k<=n;k++) { for (int i=1;i<=cnt;i++) for (int j=i;j<=cnt;j++) if (l[k]>=i&&r[k]<=j) ans1[k]=max(ans1[k],dp[i][j]); } printf("%d\n",ans); for (int i=1;i<=n;i++) printf("%d\n",ans1[i]); }
