题解 P1295 【[TJOI2011]书架】

发个O(n)的题解 先写个dp方程f[i]=f[j]+max(a[j+1]...a[i])(s[i]-s[j]<=m) 对于转移方程可行的j且a[j+1]<=max(a[j+2]...a[i]) f[j]+max(a[j+1]...a[i])与f[j+1]+max(a[j+2]...a[i])后半段相同 易知f[j]<=f[j+1],所以前者更优 推广可得最优转移一定在a[q1]>a[q2]>a[q3]>a[q4]>...>a[qj]中 f[a[qj]]+a[q[j+1]]取得（对于a[q1],有f[st]+a[q1],st是最大的使a[st]+...+a[i]>m） 即维护一个单调队列，并对单调队列中值取最大值 即维护一个可查询最大值的双端队列（单调队列是个双端队列） 操作是维护一个中点，向两端维护单调栈，如果左右端点超过中点就重构单调栈， 以上操作是O(1)的证明我放在U16395中 https://www.luogu.org/problemnew/show/U16395 所以每次就是提出双端队列中的最小值和f[st]+a[q1]取最小值，为f[i] 做到O(1)转换，总共就是O(n) ```cpp #include<cstdio> using namespace std; #define fo(a,b,c) for(int a=b;a<=c;a++) #define go(a,b,c) for(int a=b;a>=c;a--) #define min(a,b) ((a)<(b)?(a):(b)) int read(){ int a=0,f=0;char c=getchar(); for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1; for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0'; return f?-a:a; } const int N=1e5+1; int a[N],f[N],qu[N],qi[N],pst[N],qst[N],pt,qt,s=1,t,mid; //a数字，f最优解，qi单降队列在a的下标，qu对qi每个的f值，pst左单调栈在qu的下标，qst表示右 void pushp(int x){ if(!pt||qu[pst[pt]]>qu[x])pst[++pt]=x; }//左端插入 void pushq(int x){ if(!qt||qu[qst[qt]]>qu[x])qst[++qt]=x; }//右端插入 void rebuild(){ mid=s+t>>1;pt=qt=0; go(i,mid,s)pushp(i); fo(i,mid+1,t)pushq(i); }//重构单调栈 int main(){ //f[i]=f[j]+max(a[j+1]...a[i])(s[i]-s[j]<=m)动归方程 int n=read(),m=read(),st=1,sum=0; fo(i,1,n){ sum+=a[i]=read(); while(sum>m)sum-=a[st++];//维护st while(s<=t&&a[qi[t]]<=a[i]){ if(qt&&qst[qt]==t)qt--; if(pt&&pst[pt]==t)pt--; if(--t<=mid)rebuild(); }//维护单调队列 qi[++t]=i;qu[t]=(s==t?f[st-1]:f[qi[t-1]])+a[i];pushq(t);//加入当前元素 if(pst[pt]==s)pt--; if(qst[qt]==s)qt--;//将a[q1]排除（不符合f[a[qj]]+a[q[j+1]]规律） while(s<=t&&qi[s]<st){ if(qt&&qst[qt]==s)qt--; if(pt&&pst[pt]==s)pt--; if(++s>mid)rebuild(); }//弹出过期元素 f[i]=a[qi[s]]+f[st-1]; if(pt)f[i]=min(f[i],qu[pst[pt]]); if(qt)f[i]=min(f[i],qu[qst[qt]]);//转移 } printf("%d",f[n]); return 0; } //input //6 6 //3 5 1 2 4 1 //output //13 ```