洛谷題目傳送門
DP題怕是都要大大的腦洞。。。。。。
首先,時間那麼大沒用,直接離散化。
第一問還好。根據題意容易發現,當一堆活動的時間有大量重疊的時候,更好的辦法是把它們全部安排到一邊去。那麼我們轉移的時候也肯定是要一塊一塊地轉移啦。
設\(tot_{l,r}\)為完全被包含在\(l-r\)時間内活動總數,直接\(O(n^3)\)暴力求就好了。
設\(pre_{i,j}\)為時間\(1-i\)内一邊選\(j\)個時,另一邊能選的最大值。枚舉一塊轉移的話,我們的方程應該寫成這樣:
\[pre_ {i,j}=\max\limits_{k=1}^i\{pre_ {k,j}+tot_{k,i},pre _{k,j-tot _{k,i}}\}
\]
(顯然兩種情況都要考慮)
然後答案就是\(\max\limits_{j=1}^n\{\min(pre_{m,j},j)\}\)啦(\(m\)為離散化後的時間總長,不會超過\(2n\))
這個數組為什麼要叫\(pre\)呢?這是個字首DP值。為了第二問,我們還要做個字尾DP,\(suf_{i,j}\)表示時間\(i-m\)内一邊選\(j\)個時,另一邊能選的最大值,跟\(pre\)幾乎一樣的轉移,也是\(O(n^3)\)的。
對于第二問,我們顯然可以肯定\(s_i-t_i\)之内的活動都被一邊選走了。至于\(s_i\)之前和\(t_i\)以後選了多少,我們也隻好枚舉。設\(f_{l,r}\)為一邊強制選\(l-r\)之間所有活動時最優的最小值,假定這一邊在前面選了\(x\)個,在後面選了\(y\)個,另一邊最多能選多少也就知道了,有方程
\[f_{l,r}=\max\limits_{x=1}^m\max\limits_{y=1}^m\{\min(x+tot_{l,r}+y,pre_{l,x}+suf_{r,y})\}
然後第\(i\)個的答案就是\(f_{s_i,t_i}\)麼?注意千萬别掉入這個誤區!\(pre\)和\(suf\)隻是保證了局部最優,而沒有保證全局最優。要說人話的話,就是可能有一個活動跨過了\(s_i\),然而\(f_{s_i,t_i}\)并沒有統計到它,隻有擴大強制選的區間使得能夠包含它,才能統計到最優解。于是需要枚舉強制選區間了,\(ans_i=\max\limits_{l=1}^{s_i}\max\limits_{r=t_i}^m\{f_{l,r}\}\)
這樣的話,整個\(f\)都必須要算出來,上面的枚舉算法就變成\(O(n^4)\)了,跑不動。
點開标簽發現有單調隊列?!蒟蒻就往單調性上面想了想,于是就有了一個結論:設枚舉\(x\)時有一個使答案最優的\(y\),那麼當\(x\)增大時,如果\(y\)也增大那麼答案不會更優。觀察上面那個式子\(\min(x+tot_{l,r}+y,pre_{l,x}+suf_{r,y})\),那麼因為\(pre,suf\)都是遞減的,是以很顯然我們不能讓\(x,y\)變大而\(pre,suf\)變小。
于是,實作的時候,隻要把\(y\)從大往小掃了,并不需要什麼單調隊列來維護它。
#include<cstdio>
#include<algorithm>
#define RG register
#define R RG int
#define G c=getchar()
#define Upd(A,L,R) {chkmx(A[i][j],A[k][j]+tot[L][R]); \
if(j>=tot[L][R])chkmx(A[i][j],A[k][j-tot[L][R]]);}
#define Calc(y) min(x+tot[l][r]+y,pre[l][x]+suf[r][y])
using namespace std;
const int N=209,M=409,INF=1e9;
int s[N],t[N],b[M],tot[M][M],pre[M][N],suf[M][N],f[M][M];
inline int in(){
RG char G;
while(c<'-')G;
R x=c&15;G;
while(c>'-')x=x*10+(c&15),G;
return x;
}
inline int min(R x,R y){return x<y?x:y;}
inline void chkmx(R&x,R y){if(x<y)x=y;}
int main(){
R n=in(),m=0,i,j,k,l,r,x,y,p0,p1,ans;
for(i=1;i<=n;++i){
b[++m]=s[i]=in();
b[++m]=t[i]=in()+s[i];
}
sort(b+1,b+m+1);//離散化
m=unique(b+1,b+m+1)-b-1;
for(i=1;i<=n;++i){
s[i]=lower_bound(b+1,b+m+1,s[i])-b;
t[i]=lower_bound(b+1,b+m+1,t[i])-b;
for(l=1;l<=s[i];++l)//tot暴力求
for(r=m;r>=t[i];--r)++tot[l][r];
}
for(i=1;i<=m;++i)//注意初始化
for(j=1;j<=n;++j)pre[i][j]=suf[i][j]=-INF;
for(i=1;i<=m;++i)
for(j=0;j<=tot[1][i];++j)
for(k=1;k<=i;++k)Upd(pre,k,i);
for(i=m;i;--i)//轉移很相似,搞了個宏定義
for(j=0;j<=tot[i][m];++j)
for(k=i;k<=m;++k)Upd(suf,i,k);
for(l=1;l<=m;++l)
for(r=l+1;r<=m;++r)
for(y=n,x=0;x<=n;++x){
p0=Calc(y);//p0為最優決策,p1為目前決策
while(y&&p0<=(p1=Calc(y-1)))p0=p1,--y;
chkmx(f[l][r],Calc(y));
}
ans=0;
for(j=1;j<=n;++j)chkmx(ans,min(pre[m][j],j));
printf("%d\n",ans);
for(i=1;i<=n;++i){
ans=0;
for(l=1;l<=s[i];++l)
for(r=m;r>=t[i];--r)chkmx(ans,f[l][r]);
printf("%d\n",ans);
}
return 0;
}