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

題意:兩個會場不能同時表演，但是同一個時間可以同時表演，要求讓兩個會場表演數(shù)量最小的最大，然后限制某一個必須表演，最小的要最大是多少。。

思路：先將時間離散化，預(yù)處理數(shù)組num[i][j],代表時間i到時間j一共包含了幾個表演。

然后進(jìn)行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]]) 后兩個分別代表這個區(qū)間的表演放到B，和這個區(qū)間的表演放到A，

suf[i][j]代表i~時間m，會場A表演了j個，此時會場B最多能表演幾個，這個就是同理了

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

對于第二問，我們考慮這樣設(shè)計(jì):

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

這樣的轉(zhuǎn)移是n^4的，不能通過全部數(shù)據(jù)。

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

再令x固定，y逐漸增大，發(fā)現(xiàn)f[x][y]是單峰的！，因此當(dāng)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]會達(dá)到最接近，然后此時就是最大的答案，之前的和之后的都不是最優(yōu)的！

1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #include<cstring> 5 #include<algorithm> 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 else 22 if (p[mid]<x) l=mid+1; 23 else r=mid-1; 24 } 25 return 0; 26 } 27 void init(){ 28 n=read(); 29 for (int i=1;i<=n;i++) 30 a[i].s=read(),a[i].e=read()+a[i].s,p[++p[0]]=a[i].s,p[++p[0]]=a[i].e; 31 std::sort(p+1,p+1+p[0]); 32 int j=1; 33 for (int i=2;i<=p[0];i++) 34 if (p[i]!=p[j]) p[++j]=p[i]; 35 p[0]=j; 36 for (int i=1;i<=n;i++) a[i].s=find(a[i].s),a[i].e=find(a[i].e); 37 for (int i=1;i<=p[0];i++) 38 for (int j=i;j<=p[0];j++) 39 for (int k=1;k<=n;k++) 40 if (i<=a[k].s&&a[k].e<=j) num[i][j]++; 41 } 42 void dp(){ 43 for (int i=0;i<=500;i++) 44 for (int j=0;j<=500;j++) 45 pre[i][j]=suf[i][j]=-1000000000; 46 pre[0][0]=suf[p[0]+1][0]=0; 47 for (int i=1;i<=p[0];i++) 48 for (int k=i;k>=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]<sx){ 68 ans[i][j]=sx; 69 }else break; 70 }else break; 71 } 72 } 73 void Output(){ 74 int Ans=0; 75 for (int i=1;i<=n;i++) 76 Ans=std::max(std::min(pre[p[0]][i],i),Ans); 77 printf("%d\n",Ans); 78 for (int i=1;i<=n;i++){ 79 Ans=0; 80 for (int j=1;j<=p[0];j++) 81 for (int k=j;k<=p[0];k++) 82 if (j<=a[i].s&&a[i].e<=k) Ans=std::max(Ans,ans[j][k]); 83 printf("%d\n",Ans); 84 } 85 } 86 int main(){ 87 init(); 88 dp(); 89 Output(); 90 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/qzqzgfy/p/5610206.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2436 NOI嘉年华(单调优化)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。