为什么这么多dp！！！
Bottles
1.一道背包问题（还涉及贪心）
2.考虑转移方程，在这道题中，关键变量只有两个 a , b 。第一问很好求，根据贪心，先对瓶子的容量进行降序排序，求前若干个瓶子使他们的容量大于等于所有水的体积时的个数即可。
在选择瓶子最少的情况下，方案是不一定的。通过观察得知， 第二问就是要在第一问的个数确定时，求出选择瓶子的水最多的方案 。选择了若干个瓶子，就意味着其他的瓶子的水要倒入其中，花费就为他们水的体积之和 。然后，考虑转移方程。设 fi 表示当水的体积是 i 时所需要的最少的瓶子数。
显然，根据一般的背包问题，有 fi=maxf i−bj +1 。
同时，根据上面的分析，我们要求的是此时水体积最大的，所以附加上一个 ans 数组， ansi 表示 ansi 表示当容积为 i 时水体积的最大值 。
#include<bits/stdc++.h>
using namespace std;
const int N=110;
struct node{int a,b;
}c[N];
int n,ans,suma,sumb,k=0,f[N*N][N];
bool cmp(node x,node y){return x.b>y.b;
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>c[i].a;suma+=c[i].a;}for(int i=1;i<=n;i++) cin>>c[i].b;sort(c+1,c+n+1,cmp);while(sumb<suma) sumb+=c[++k].b;cout<<k<<" ";memset(f,128,sizeof(f));f[0][0]=0;//cout<<f[1][1]<<endl;for(int i=1;i<=n;i++)for(int j=sumb;j>=c[i].b;j--)for(int kk=1;kk<=k;kk++){f[j][kk]=max(f[j][kk],f[j-c[i].b][kk-1]+c[i].a);}for(int i=suma;i<=sumb;i++) ans=max(ans,f[i][k]);cout<<suma-ans;return 0;
}上课
1.贪心题
2.拆方差的式子，方差等于平方的平均减平均的平方。因为总和固定，所以平均的平方固定，所以最小化平方和即可。假设当前对于 x 已求出最小方差的序列，要求 x+1 的最小方差。因为要最小化平方和，所以要把最小的能加的位置加一。原因是平方和公式增加的量是两倍的原数，所以要原数尽可能小。把初始状态全部取 li，然后考虑增量即可。每次把 x 加上一太慢了，考虑对区间按位处理。记录当前位置有多少个区间可以用来加一。
方差式子整理之后就是：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10,mx=1e6,mod=998244353;
struct query{ll x,id,ans;friend bool operator<(query xy,query zb){return xy.x<zb.x;}
}qq[N];
ll n,q,invn,l[N],r[N],cnt[N],ans,ansx;
inline ll p(ll x,ll y){if(!y) return 1;if(y&1) return p(x,y^1)*x%mod;return p(x*x%mod,y>>1);
}
int main(){scanf("%lld%lld",&n,&q);invn=p(n,mod-2);for(ll i=1;i<=n;i++){scanf("%lld%lld",&l[i],&r[i]);ans+=l[i]*l[i];ansx+=l[i];cnt[l[i]+1]++;cnt[r[i]+1]--;}for(ll i=0;i<=mx;i++) cnt[i]+=cnt[i-1];for(ll i=1;i<=q;i++){scanf("%lld",&qq[i].x);qq[i].id=i;}sort(qq+1,qq+q+1);for(ll i=1,j=0;i<=q;i++){while(ansx<qq[i].x){if(qq[i].x-ansx<cnt[j]){cnt[j]-=(qq[i].x-ansx);(ans+=(qq[i].x-ansx)*(j*2-1)%mod)%=mod;ansx=qq[i].x;break;}ansx+=cnt[j];(ans+=cnt[j]*(j*2-1)%mod)%=mod;j++;}qq[i].ans=ans;qq[i].x%=mod;}sort(qq+1,qq+q+1,[](query xy,query zb){return xy.id<zb.id;});for(ll i=1;i<=q;i++)printf("%lld\n",(qq[i].ans*invn%mod-qq[i].x*qq[i].x%mod*invn%mod*invn%mod+mod)%mod);return 0;
}Pictures with Kittens (hard version)
1.单调队列优化dp。
2.用 f[i][j] 表示前 i 个数一共取 j 个且第 i 个一定取所得到的最大答案。
不难写出转移方程：f[i][j]=max{f[p][j−1]}+a[i](i−k≤p<i)
考虑优化：
注意到可以转移的区间长度不变，要求的是区间 [i−k,i−1] 内的最小值，可以采用单调队列。
tips：通过单调队列，第一次更新即为最优答案，如果不进行初始化，但是本题可能会存在一种情况，即非法情况可能转移至合法情况，导致答案非法，说的清楚一点，即转移中可能会存在同一个数被加多次的情况，开始把 f 数组赋为负无穷，否则得到的答案可能比正确答案大。
记得特判。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5010;
int n,k,x,le=1,ri=0;
ll f[N][N];
int q[N],a[N];
int main(){scanf("%d%d%d",&n,&k,&x);for(int i=1;i<=n;i++) scanf("%d",&a[i]);memset(f,0xcf,sizeof(f));if(n/k>x){puts("-1");return 0;}f[0][0]=0;for(int j=1;j<=x;j++){le=1,ri=0;q[++ri]=0;for(int i=1;i<=n;i++){while(le<=ri&&q[le]+k<i) le++;f[i][j]=f[q[le]][j-1]+a[i];while(le<=ri&&f[i][j-1]>=f[q[ri]][j-1]) ri--;q[++ri]=i;}}ll ans=0;for(int i=n-k+1;i<=n;i++) ans=max(ans,f[i][x]);printf("%lld\n",ans);return 0;
}Bookshelf G
1.线段树优化dp（怎么这么多dp！）
2.设 fi 表示前 i 本书满足条件时书架高度和的最小值。那么对于当前位置 i，满足宽度限制的最小位置 w 一定不减，可以用指针维护。显然有 fi=min{fj−1+max{Hj,⋯,Hi}}(w≤j≤i)。
把原来的 Hj 变为 Hj∼Hi 的最大值，显然要动态维护 Hw∼Hi 的值，只需支持对 H 后缀取 max 操作。由于 H 的最大值是不增的，所以取 max 相当于对一段后缀做区间覆盖。
线段树上二分找到当前要取 max 的分界点，剩下的前缀不会被影响。还需维护区间内 fi 的 min 和 fi+Hi 的 min，以及查询 w∼i 中最小的 fi+Hi。
都可以用线段树来维护。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
struct node{int l,r,f,sum,lazy;
}e[N<<2];
int n,w[N],h[N],m,f[N];
int pre[N],st[N],top,L;
void pushup(int u){e[u].f=min(e[u<<1].f,e[u<<1|1].f);e[u].sum=min(e[u<<1].sum,e[u<<1|1].sum);return;
}
void pushdown(int u){if(e[u].lazy){e[u<<1].lazy=e[u<<1|1].lazy=e[u].lazy;e[u<<1].sum=e[u<<1].f+e[u].lazy;e[u<<1|1].sum=e[u<<1|1].f+e[u].lazy;e[u].lazy=0;}return;
}
void build(int u,int l,int r){e[u].l=l,e[u].r=r;if(l==r) return;int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);return;
}
void insert(int u,int x,int val){if(e[u].l==e[u].r){e[u].f=e[u].sum=val;return;}pushdown(u);int mid=e[u].l+e[u].r>>1;if(x<=mid) insert(u<<1,x,val);else insert(u<<1|1,x,val);pushup(u);return;
}
void update(int u,int l,int r,int val){if(l<=e[u].l && e[u].r<=r){e[u].lazy=val;e[u].sum=e[u].f+val;return;} pushdown(u);int mid=e[u].l+e[u].r>>1;if(l<=mid) update(u<<1,l,r,val);if(r>mid) update(u<<1|1,l,r,val);pushup(u);return;
}
int query(int u,int l,int r){if(l<=e[u].l && e[u].r<=r) return e[u].sum;pushdown(u);int mid=e[u].l+e[u].r>>1;int res=1e18;if(l<=mid) res=min(res,query(u<<1,l,r));if(r>mid) res=min(res,query(u<<1|1,l,r));return res;
}
signed main(){cin>>n>>L;for(int i=1;i<=n;i++) cin>>h[i]>>w[i];for(int i=2;i<=n;i++) w[i]+=w[i-1];for(int i=1;i<=n;i++){while(top&&h[i]>h[st[top]]) top--;if(top) pre[i]=st[top];else pre[i]=1;st[++top]=i;}build(1,1,n);int head=0,nowmaxn=0;for(int i=1;i<=n;i++){nowmaxn=max(nowmaxn,h[i]);while(w[i]-w[head]>L) head++;update(1,pre[i],i-1,h[i]);if(head==0){f[i]=query(1,head+1,i-1);f[i]=min(f[i],nowmaxn);}else f[i]=query(1,head,i-1);insert(1,i,f[i]);}printf("%lld\n",f[n]);return 0;
}总之，dp题挺多的（1道背包，1道单调队列优化，1道线段树优化），不太好写暴力，就当练习dp了。
