JZOJ 5347. 遥远的金字塔
Description
Input
Output
Sample Input
5 3 1 6 1 5 3 5 4 4 4 4
Sample Output
15
Data Constraint
做法：
其实这就是很明显的一道斜率优化的dp式子，我们首先可以得到最显然的dp方程，设f[i][j]表示前i层数分成j个不相交的矩形的最大面积，那么我们有：
f[i][j]=max(f[i-k+1][j-1]+(y[i]-x[i])*k)，k为与当前这一块联通的矩形宽。
这个式子等价于f[i][k]=max(f[j][k-1]+(y[i]-x[i])*(i-j))，然后就可以斜率优化了（证明？我也忘了。。）
然后事实上转移只跟上一层有关，所以只用两个数组就好啦。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #define N 20007 5 #define LL long long 6 using namespace std; 7 int n,m,q[N]; 8 LL f[N],g[N],w[N],ans; 9 10 int main(){ 11 freopen("pyramid.in","r",stdin); 12 freopen("pyramid.out","w",stdout); 13 scanf("%d%d",&n,&m); 14 for (int i=1;i<=n;i++){ 15 int x,y; 16 scanf("%d%d",&x,&y); 17 w[i]=y-x+1; 18 } 19 for (int i=1;i<=n;i++) f[i]=-1e14; 20 for (int i=1;i<=m;i++){ 21 int head=0,tail=0; 22 q[0]=0; 23 for (int i=1;i<=n;i++){ 24 for(;(head<tail)&&(f[q[head+1]]-f[q[head]]>w[i]*(q[head+1]-q[head]));head++); 25 g[i]=f[q[head]]+w[i]*(i-q[head]); 26 if (i!=n){ 27 for(;(head<tail)&&((f[q[tail]]-f[q[tail-1]])*(i-q[tail])<(f[i]-f[q[tail]])*(q[tail]-q[tail-1]));tail--); 28 q[++tail]=i; 29 } 30 } 31 for (int i=1;i<=n;f[i]=g[i],i++); 32 } 33 for (int i=1;i<=n;i++) ans=ans>f[i]?ans:f[i]; 34 printf("%lld",ans); 35 }