http://www.lydsy.com/JudgeOnline/problem.php?id=2436

题意:两个会场不能同时表演，但是同一个时间可以同时表演，要求让两个会场表演数量最小的最大，然后限制某一个必须表演，最小的要最大是多少。。

思路：先将时间离散化，预处理数组num[i][j],代表时间i到时间j一共包含了几个表演。

然后进行dp,pre[i][j]，代表1~时间i，会场A表演了j个，此时会场B最多能表演几个。

pre[i][j]=max(pre[i][j+1],pre[k][j]+num[k][i],pre[k][j-num[k][i]]) 后两个分别代表这个区间的表演放到B，和这个区间的表演放到A，

suf[i][j]代表i~时间m，会场A表演了j个，此时会场B最多能表演几个，这个就是同理了

然后第一问的答案就是max(min(i,pre[m][i]))

对于第二问，我们考虑这样设计:

ans[i][j]=max(min(x+y+num[i][j],pre[i][x]+suf[j][y]))

这样的转移是n^4的，不能通过全部数据。

我们考虑令i和j固定，f[x][y]=min(x+y+num[i][j],pre[i][x]+suf[j][y])

再令x固定，y逐渐增大，发现f[x][y]是单峰的！，因此当f[x][y+1]<f[x][y]就可以break了。

原因是x+y+num[i][j]中只有y是在不断增大的，而pre[i][x]+suf[j][y]中suf[j][y]是不断减小的，由于是取min

因此会有一个瞬间x+y+num[i][j]和pre[i][x]+suf[j][y]会达到最接近，然后此时就是最大的答案，之前的和之后的都不是最优的！

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 struct node{ 7     int s,e; 8 }a[200005]; 9 int p[200005],ans[505][505],n,suf[505][505],pre[505][505],num[505][505];10 int read(){11      int t=0,f=1;char ch=getchar();12      while (ch<'0'||ch>'9') {
   if (ch=='-') f=-1;ch=getchar();}13      while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}14      return t*f;15 }16 int find(int x){17      int l=1,r=p[0];18      while (l<=r){19          int mid=(l+r)>>1;20          if (p[mid]==x) return mid;21              else22                  if (p[mid]
          
           =0;k--){49 pre[i][k]=pre[i][k+1];50 for (int j=0;j<=i-1;j++)51 pre[i][k]=std::max(pre[i][k],std::max(pre[j][k]+num[j][i],pre[j][k-num[j][i]]));52 }53 for (int i=p[0];i>=1;i--)54 for (int k=p[0]-i+1;k>=0;k--){55 suf[i][k]=suf[i][k+1];56 for (int j=i+1;j<=p[0]+1;j++)57 suf[i][k]=std::max(suf[i][k],std::max(suf[j][k]+num[i][j],suf[j][k-num[i][j]]));58 } 59 for (int i=1;i<=p[0];i++)60 for (int j=i;j<=p[0];j++){61 int k=1+p[0]-j; 62 for (int x=0;x<=i;x++)63 for (int y=0;y<=k;y++)64 if (x+y<=n){65 int sx=std::min(x+y+num[i][j],pre[i][x]+suf[j][y]);66 if (sx<0) break;67 if (ans[i][j]