ZR 集训 Day10 - DP 优化 · ooliver

ZR 集训 Day10 - DP 优化 P1886 【模板】单调队列 / 滑动窗口模板，不知道为啥之前一直 20 pts。 C++ #include using namespace std; const int N=1e6+5; int n,k; int a[N],q[N]; void get(int y){ int l=0,r=0; for(int i=1;i=a[i]) r--; q[++r]=i; while(lk) l++; if(i>=k) cout>n>>k; for(int i=1;i>a[i]; get(1); cout `#include using namespace std; const int N=1e6+5; int n,k; int a[N],q[N]; void get(int y){ int l=0,r=0; for(int i=1;in;i++){ while(lr&&a[q[r]]>=a[i]) r--; q[++r]=i; while(lr&&i-q[l]+1>k) l++; if(i>=k) couty*a[q[l]]" "; } } signed main(){ cin>>n>>k; for(int i=1;in;i++) cin>>a[i]; get(1); cout"\n"; for(int i=1;in;i++) a[i]=-a[i]; get(-1); return 0; } ` P1776 宝物筛选单调队列优化多重背包。 \begin{aligned} dp[i]&=\max\{dp[i-kw]+kv\} \\ dp[i]&=\max\{dp[i-kw]-\frac{(i-kw)v}{w}\}+\frac{iv}{w} \end{aligned} 转化成滑动窗口后用单调队列优化。代码： C++ #include using namespace std; const int N=105,M=1e5+5; int n,W; int q[M],dp[N][M]; int main(){ cin>>n>>W; for(int i=1;i>v>>w>>m; for(int j=0;jm) l++; if(l `#include using namespace std; const int N=105,M=1e5+5; int n,W; int q[M],dp[N][M]; int main(){ cin>>n>>W; for(int i=1;in;i++){ int v,w,m; cin>>v>>w>>m; for(int j=0;jw;j++){ int l=0,r=-1; for(int k=j;kW;k+=w){ while(lr&&(k-q[l])/w>m) l++; if(lr) dp[i][k]=max(dp[i-1][k],dp[i-1][q[l]]+(k-q[l])/w*v); else dp[i][k]=dp[i-1][k]; while(lr&&dp[i-1][q[r]]-q[r]*v/wdp[i-1][k]-k*v/w) r--; q[++r]=k; } } } coutdp[n][W]; return 0; }` P3195 [HNOI2008] 玩具装箱斜率优化 DP 模板题。先推转移方程，这里设 sum 是 C 的前缀和数组： dp_i=\min\{dp_j+(i-j-1+sum_i-sum_j-L)^2\} 令 A_i=sum_i+i,B_i=sum_j+j+L+1，有： \begin{aligned} dp_i&=\min\{dp_j+(A_i-B_j)^2\} \\ dp_i&=\min\{-A_iB_j+B_j^2+dp_j\}+A_i^2 \end{aligned} 这是我们把每个 (B_j,B_j^2+dp_j) 作为一个点加入平面直角坐标系，对于一次询问，相当于查询经过每个点的斜率为 A_i 的直线的斜率最大是多少。观察这幅图，对于任何斜率，可能产生贡献的点一定在凸包上，并且链接这个点的两条线一个斜率小于查询斜率，一个斜率大于查询斜率，这其实我们使用单调队列，每次查询后弹出队列内斜率小于当前斜率的点，加点时维护下凸包。代码： C++ #include using namespace std; using ll=long long; const int N=5e4+5; ll n,L,l=1,r; ll a[N],dp[N],q[N]; struct node{ ll x,y; }d[N]; __int128 mul(node a,node b,node c){ __int128 x1=b.x-a.x,y1=b.y-a.y,x2=c.x-b.x,y2=c.y-b.y; return x1*y2-x2*y1; } signed main(){ cin>>n>>L; for(int i=1;i>a[i],a[i]+=a[i-1]; d[0]={L+1,(L+1)*(L+1)}; q[++r]=0; for(int i=1;i `#include using namespace std; using ll=long long; const int N=5e4+5; ll n,L,l=1,r; ll a[N],dp[N],q[N]; struct node{ ll x,y; }d[N]; __int128 mul(node a,node b,node c){ __int128 x1=b.x-a.x,y1=b.y-a.y,x2=c.x-b.x,y2=c.y-b.y; return x1*y2-x2*y1; } signed main(){ cin>>n>>L; for(int i=1;in;i++) cin>>a[i],a[i]+=a[i-1]; d[0]={L+1,(L+1)*(L+1)}; q[++r]=0; for(int i=1;in;i++){ ll A=i+a[i],B=i+a[i]+1+L; while(lr&&(__int128(d[q[l+1]].y-d[q[l]].y))__int128(2*A*(d[q[l+1]].x-d[q[l]].x))) l++; dp[i]=A*A+d[q[l]].y-2*A*d[q[l]].x; d[i].x=B,d[i].y=B*B+dp[i]; while(lr&&mul(d[q[r-1]],d[q[r]],d[i])0) r--; q[++r]=i; } coutdp[n]; return 0; }` P2900 [USACO08MAR] Land Acquisition G 先去掉那些被偏序了的点，之后不难想到一定是把一段排序后连续的区间放在一起购买，得到转移方程： dp_i=\min\{dp_j+y_{j+1}*x_{i}\} 一眼斜率优化，但是这里展示高科技：李超线段树。每次求 x_i 这个位置的最小值，并插入一条新直线。代码： C++ #include using namespace std; #define int long long #define lc p>1; build(lc,l,mid); build(rc,mid+1,r); } void upd(int p,int x){ int mid=(tr[p].l+tr[p].r)>>1; if(f(x,mid)>1; int res=f(tr[p].ln,x); if(x>n; for(int i=1;i>p[i].w>>p[i].l; sort(p+1,p+n+1); for(int i=1;i `#include using namespace std; #define int long long #define lc p #define rc p const int N=5e4+5; const int M=1e6+5; const int INF=2e18; int n,m; int dp[N]; struct land{ int w,l; bool operatorconst land &o)const{ if(w!=o.w) return wo.w; return lo.l; } }p[N],a[N]; struct line{ int k,b; }lne[N]; struct tree{ int l,r,ln; }tr[M2]; int f(int id,int x){ if(!id) return INF; return lne[id].k*x+lne[id].b; } void build(int p,int l,int r){ tr[p].l=l,tr[p].r=r; if(l==r) return; int mid=(l+r)>>1; build(lc,l,mid); build(rc,mid+1,r); } void upd(int p,int x){ int mid=(tr[p].l+tr[p].r)>>1; if(f(x,mid)f(tr[p].ln,mid)) swap(tr[p].ln,x); if(tr[p].l==tr[p].r) return; if(f(x,tr[p].l)f(tr[p].ln,tr[p].l)) upd(lc,x); else if(f(x,tr[p].r)f(tr[p].ln,tr[p].r)) upd(rc,x); } int qry(int p,int x){ if(tr[p].l==tr[p].r) return f(tr[p].ln,x); int mid=(tr[p].l+tr[p].r)>>1; int res=f(tr[p].ln,x); if(xmid) return min(res,qry(lc,x)); else return min(res,qry(rc,x)); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1;in;i++) cin>>p[i].w>>p[i].l; sort(p+1,p+n+1); for(int i=1;in;i++){ while(m&&a[m].lp[i].l) m--; a[++m]=p[i]; } build(1,1,1000000); lne[1]={a[1].l,0}; upd(1,1); for(int i=1;im;i++){ dp[i]=qry(1,a[i].w); if(im){ lne[i+1]={a[i+1].l,dp[i]}; upd(1,i+1); } } coutdp[m]"\n"; return 0; }` P5785 [SDOI2012] 任务安排这题的特殊点就是询问不是单调的，所以我们要保留凸包上的所有点，询问时在凸包上二分即可。代码： C++ #include using namespace std; #define int long long const int N=3e5+5; int n,s,r; int t[N],c[N],q[N],dp[N]; int find(int k){ int l=1,rr=r; while(l>1; if(dp[q[mid+1]]-dp[q[mid]]>n>>s; for(int i=1;i>t[i]>>c[i]; t[i]+=t[i-1],c[i]+=c[i-1]; } q[++r]=0; for(int i=1;i=2&&(dp[i]-dp[q[r]])*(c[q[r]]-c[q[r-1]]) `#include using namespace std; #define int long long const int N=3e5+5; int n,s,r; int t[N],c[N],q[N],dp[N]; int find(int k){ int l=1,rr=r; while(lrr){ int mid=(l+rr)>>1; if(dp[q[mid+1]]-dp[q[mid]]k*(c[q[mid+1]]-c[q[mid]])) l=mid+1; else rr=mid; } return q[l]; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>s; for(int i=1;in;i++){ cin>>t[i]>>c[i]; t[i]+=t[i-1],c[i]+=c[i-1]; } q[++r]=0; for(int i=1;in;i++){ int j=find(t[i]+s); dp[i]=dp[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]); while(r>=2&&(dp[i]-dp[q[r]])*(c[q[r]]-c[q[r-1]])(dp[q[r]]-dp[q[r-1]])*(c[i]-c[q[r]])) r--; q[++r]=i; } coutdp[n]"\n"; return 0; }` CF321E Ciel and Gondolas 设 c_{i,j} 表示第 i 个人到第 j 个人的陌生度之和，显然是等于 u_{i,i} 加到 u_{j,j} 再除以 2，可以通过二维前缀和求的的，并且 c_{i,j} 满足四边形不等式。设 dp_{i,j} 表示选了 i 组，共 j 人的最小方案数，得到转移方程： dp_{i,j}=\min\{dp_{i-1,k}+w(k+1,j)\} 显然是满足决策单调性的，就可以进行优化。代码： C++ #include using namespace std; #define int long long const int N=4e3+5,M=805; int n,k; int a[N][N],d[M][N],dp[M][N]; int read(){ int k=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c>1; } signed main(){ n=read(),k=read(); for(int i=1;i=1;j--){ int mn=dp[i][j],id; for(int l=d[i-1][j];l `#include using namespace std; #define int long long const int N=4e3+5,M=805; int n,k; int a[N][N],d[M][N],dp[M][N]; int read(){ int k=0,f=1; char c=getchar(); while(c'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c'9') k=k*10+c-'0',c=getchar(); return k*f; } void put(int x){ if(x0) putchar('-'),x=-x; if(x10) putchar(x+'0'); else put(x/10),putchar(x%10+'0'); } int w(int l,int r){ return (a[r][r]-a[r][l-1]-a[l-1][r]+a[l-1][l-1])>>1; } signed main(){ n=read(),k=read(); for(int i=1;in;i++) for(int j=1;jn;j++) a[i][j]=read(); for(int i=1;in;i++) for(int j=1;jn;j++) a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1]; memset(dp,0x3f,sizeof dp); dp[0][0]=0; for(int i=1;ik;i++){ d[i][n+1]=n; for(int j=n;j>=1;j--){ int mn=dp[i][j],id; for(int l=d[i-1][j];ld[i][j+1];l++) if(dp[i-1][l]+w(l+1,j)mn) mn=dp[i-1][l]+w(l+1,j),id=l; dp[i][j]=mn,d[i][j]=id; } } put(dp[k][n]); return 0; }`