套路：把转移方程推到只有关\(i,j\),与\(i,j\)的乘积时(由\(j\)转移到\(i\)),把只与\(i\)有关的量放到一起作截距\(B\),只与\(j\)相关的量作已知点的纵坐标\(Y\),\(i,j\)的乘积中常量与\(i\)相关量的乘积作斜率\(K\),\(j\)相关量作已知点的横坐标\(X\)，再进行线性规划
1.\((O(n^2)\)可过题）
一批任务的准备时间会影响从这批任务开始的所有任务的结束时间\[f[i]=min_{0\le j<i}\{f[j]+SumT[i]*(SumC[i]-SumC[j])+s*(SumC[n]-SumC[j])\}\]（斜率优化+\(cdq\)分治）2.
\[f_i=max_{0\le j<i}\{f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\}\] 变形一下\[f_i=f_j+as_i^2-2as_is_j+as_j^2+bs_i-bs_j+c\]\[f_j-as_j^2+bs_j=-2as_is_j+f_i+as_i^2+bs_i\] 令\[X_j=s_j\] \[Y_j=f_j-as_j^2+bs_j\]\[K_i=-2as_i\] \[B_i=f_i+as_i^2+bs_i\]\(\because a < 0\) ，\(\therefore K_i < 0\), 且\(K\)递增，要使\(B\)最大，维护上凸包double eps=1e-7;int dcmp(double x){if(fabs(x) <= eps) return 0; return x > 0 ? 1 : -1;}double Y(int x){return f[x]+a*s[x]*s[x]-b*s[x];}double X(int x){return s[x];}double slope(int i, int j){ double x1=X(i), y1=Y(i), x2=X(j), y2=Y(j); return (y1-y2)/(x1-x2);}int q[Maxn], l, r;void solve(){ n=read(); a=read(), b=read(), c=read(); for(int i=1; i <= n; i++) s[i]=s[i-1]+read(); l=r=1, q[1]=0; for(int i=1; i <= n; i++){ while(l < r && dcmp(slope(q[l], q[l+1]) - 1.0*a*2*s[i]) > 0) l++; f[i]=f[q[l]]+a*(s[i]-s[q[l]])*(s[i]-s[q[l]])+b*(s[i]-s[q[l]])+c; while(l < r && dcmp(slope(q[r-1], q[r])-slope(q[r], i) <= 0)) r--; q[++r]=i; } printf("%.0lf", f[n]);} 3.
令\(S_i=\sum_{j=1}^iC_j\),\(P_i=S_i+i\) 则\[f_i=min_{0\le j<i}\{f_j+(P_i-P_j-1-L)^2\}\]\[f_i=f_j+P_i^2-2P_iP_j+P_j^2-2(L+1)(P_i-P_j)+(L+1)^2\]\[f_j+P_j^2=2(P_i-L-1)P_j+f_i-P_i^2+2(L+1)P_i+(L+1)^2\] 令\[X_j=P_j\] \[Y_j=f_j+P_j^2\]\[K_i=2(P_i-L-1)\] \[B_i=f_i-P_i^2+2(L+1)P_i+(L+1)^2\]\(\because P_i > 0,\therefore K_i\)递增，要使\(B_i\)最小，维护下凸包#define a(i) (sum[i]+i)#define b(i) (a(i)+L+1)#define Y(i) (dp[i]+b(i)*b(i))#define X(i) b(i)#define slope(i, j) ((Y(i)-Y(j))/(X(i)-X(j)))int q[N], head, tail;void solve(){ n=read(), L=read(); head=tail=1; for(int i=1; i <= n; i++){ sum[i]=sum[i-1]+read(); while(head < tail && slope(q[head], q[head+1]) < 2*a(i)) head++; dp[i]=dp[q[head]]+(a(i)-b(q[head]))*(a(i)-b(q[head])); while(head < tail && slope(i, q[tail-1]) < slope(q[tail-1], q[tail])) tail--; q[++tail]=i; } printf("%lld\n", dp[n]);} 4.
令\(S_i\)为每天的路程长度，\(sum\)为总路程，先推\(vm^2\)\[\Delta S=\frac{sum}{m}\]\[vm^2=m\sum_{i=1}^m(S_i-\Delta S)^2\]\[=m\sum_{i=1}^mS_i^2-2\Delta SS_i+\Delta S^2\]\[=m\sum_{i=1}^mS_i^2-sum^2\] 所以令\(f_{(i, j)}\)为前\(i\)段路分为\(j\)天走的最小\(\sum_{i=1}^jS_i\)\[f_{(i, j)}=min_{j-1\le k<i}\{f_{(k, j-1)}+(Sum_{i}-Sum_k)^2\}\] 不管\(j\),\[f_i=f_k+Sum_i^2-2Sum_iSum_k+Sum_k^2\]\[f_k+Sum_k^2=f_i-Sum_i^2+2Sum_iSum_k\] 令\[X_k=Sum_k\] \[Y_k=f_k+Sum_k^2\]\[K_i=2Sum_i\]\[B_i=f_i-Sum_i^2\] 令\(B_i\)最小，\(\because K_i\)递增，\(\therefore\)维护下凸包int q[Maxn], l, r;ll *f=f1, *g=g1;double X(int i) {return S[i];}double Y(int i) {return g[i]+S[i]*S[i];}double slope(int i, int j){ double x1=X(i), y1=Y(i), x2=X(j), y2=Y(j); return (y1-y2)/(x1-x2);}void solve(){ n=read(), m=read(); for(int i=1; i <= n; i++) S[i]=S[i-1]+read(), f[i]=S[i]*S[i]; for(int i=1; i < m; i++){ l=r=1; q[1]=i; swap(f, g); for(int j=i+1; j <= n; j++){ while(l < r && slope(q[l], q[l+1]) <= 2.0*S[j]) l++; f[j]=g[q[l]]+(S[j]-S[q[l]])*(S[j]-S[q[l]]); while(l < r && slope(q[r], q[r-1]) >= slope(q[r], j)) r--; q[++r]=j; } } printf("%lld", f[n]*m-S[n]*S[n]);} 5.
令 \[d_i=\sum_{j=1}^iD_j, A_i=T_i-d_i\] 则\(A_i\)为接到猫\(i\)的最早出发时刻，若出发时刻为\(t\),则猫等待的时间为\(t-A_i\)，把猫按\(A\)从小到大排序，令\(S_i=\sum_{j=1}^iA_i\) ，则有每个\(feeder\)接到的为连续一段的猫最优
证明略(懒)
ll *f=f1, *g=g1;int q[Maxn], l, r;double X(int i){return i;}double Y(int i){return g[i]+S[i];}double slope(int i, int j){ double x1=X(i), x2=X(j), y1=Y(i), y2=Y(j); return (y2-y1)/(x2-x1);}void solve(){ n=read(), m=read(), p=read(); for(int i=2; i <= n; i++) D[i]=D[i-1]+read(); for(int i=1, x, t; i <= m; i++) x=read(), t=read(), A[i]=t-D[x]; sort(A+1, A+1+m); for(int i=1; i <= m; i++) S[i]=S[i-1]+A[i]; for(int i=1; i <= m; i++) f[i]=A[i]*i-S[i]; for(int i=1; i < p; i++){ q[1]=0; l=r=1; swap(f, g); for(int j=1; j <= m; j++){ while(l < r && slope(q[l], q[l+1]) <= A[j]) l++; f[j]=g[q[l]]+(j-q[l])*A[j]+S[q[l]]-S[j]; while(l < r && slope(q[r], q[r-1]) >= slope(q[r], j)) r--; q[++r]=j; } } printf("%lld", f[m]);} 6.
- 题意:求通过减小序列中元素的方式把给定序列\(a[]\)变为\(K-Anonymous\)序列的最小代价 - 定义: 1. \(K-Anonymous\)：对于\(\forall s \in a[]\),至少存在其它\(k-1\)个元素与它相等 2. 代价:把元素\(s\)变为\(s'\)的代价为\(s-s'\)\[f_i=min_{0\le j\le i-k}\{f_j+S_i-S_j-(i-j)a_{j+1}\}\]
\[f_j-S_j+ja_{j+1}=f_i-S_i+ia_{j+1}\] 令\[X_j=a_{j+1}\] \[Y_j=f_j-S_j+ja_{j+1}\]\[K_i=i\] \[B_i=f_i-S_i\] 要使\(B\)最小,\(\because K\)递增，\(\therefore\)维护下凸包(我不知道为什么用\(double\)求\(slope\)会被卡)ll Y(int i){return f[i]-S[i]+a[i]*i;}int q[Maxn], l, r;void solve(){ int T=read(); while(T--){ n=read(), k=read(); for(int i=0; i < n; i++) a[i]=read(); for(int i=1; i <= n; i++) S[i]=S[i-1]+a[i-1]; l=r=1, q[1]=0; for(int i=1; i <= n; i++){ while(l < r && (a[q[l+1]]-a[q[l]])*i >= Y(q[l+1])-Y(q[l])) l++; f[i]=f[q[l]]+S[i]-S[q[l]]+a[q[l]]*(q[l]-i); if(i-k+1 >= k) { while(l < r && (a[q[r-1]]-a[q[r]])*(Y(q[r])-Y(i-k+1)) <= (a[q[r]]-a[i-k+1])*(Y(q[r-1])-Y(q[r]))) r--; q[++r]=i-k+1; } } printf("%lld\n", f[n]); }}