题解 P4360 【[CEOI2004]锯木厂选址】

hicc0305

2018-05-02 11:27:05

Solution

一道斜率优化的DP题 先说一下几个数组的含义: s[i]表示前i棵树的重量之和 d[i]表示第i棵树到第一棵树的距离 c[i]前i棵树运到i的费用 也就是第一个锯木厂的费用就是c[i],假设第二个锯木厂设在j(j>i),那么i~j的树木运到j的费用就是c[j]-c[i]-s[i]·(d[j]-d[i]) 那么也就是说第一个建在i,第二个建在j的总费用为第一棵树到i棵数的总费用c[i],第i+1到第j棵数的总费用c[j]-c[i]-s[i]·(d[j]-d[i]),以及第j+1棵到山脚的总费用c[n+1]-c[j]-s[j]·(d[n+1]-d[j]) 加起来就是:c[n+1]-s[i]·(d[j]-d[i])-s[j]·(d[n+1]-d[j]) 我们用f[j]表示第一个锯木厂建在j的最小费用,那么f[j]=min(c[n+1]-s[i]·(d[j]-d[i])-s[i]·(d[n+1]-d[j]))(0<i<j) 当我们枚举i时,如果k比i(k>i)更优则有:c[n+1]-s[i]·(d[j]-d[i])-s[i]·(d[n+1]-d[j])>c[n+1]-s[k]·(d[j]-d[k])-s[j]·(d[n+1]-d[j]) -> s[i]·d[i]−s[k]·d[k]>d[j]∗(s[i]−s[k]) 因为k>i所以s[k]>s[i] -> (s[i]·d[i]−s[k]·d[k])/(s[i]−s[k])就可以了 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; int c[20100],s[20100],d[20100]; int q[101000],dp[20100]; double clac(int j,int k) { return (s[j]*d[j]-s[k]*d[k])/(s[j]-s[k]); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); s[i]=s[i-1]+x; c[i+1]=c[i]+s[i]*y; d[i+1]=d[i]+y; } int l=1,r=1; q[1]=0,s[n+1]=s[n]; for(int i=1;i<=n;i++) { while(l<r && clac(q[l],q[l+1])<d[i]) l++; int j=q[l]; dp[i]=c[n+1]-s[j]*(d[i]-d[j])-s[i]*(d[n+1]-d[i]); while(l<r && clac(q[r-1],q[r])>clac(q[r],i)) r--; q[++r]=i; } int ans=0x7fffffff; for(int i=1;i<=n;i++) ans=min(ans,dp[i]); cout<<ans; return 0; } ``` <d[j] 这样我们可以用单调队列来维护,在枚举i的时候,的d[j]是不变的,用单调队列来维护两点的斜率(s[i]·d[i]−s[k]·d[k])/(s[i]−s[k])就可以了 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; int c[20100],s[20100],d[20100]; int q[101000],dp[20100]; double clac(int j,int k) { return (s[j]*d[j]-s[k]*d[k])/(s[j]-s[k]); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); s[i]=s[i-1]+x; c[i+1]=c[i]+s[i]*y; d[i+1]=d[i]+y;//求出各个数组 } int l=1,r=1; q[1]=0,s[n+1]=s[n]; for(int i=1;i<=n;i++) { while(l<r && clac(q[l],q[l+1])<d[i]) l++; int j=q[l]; dp[i]=c[n+1]-s[j]*(d[i]-d[j])-s[i]*(d[n+1]-d[i]); while(l<r && clac(q[r-1],q[r])>clac(q[r],i)) r--;//单调队列维护,把斜率不优的踢出去 q[++r]=i; } int ans=0x7fffffff; for(int i=1;i<=n;i++) ans=min(ans,dp[i]); cout<<ans; return 0; } ```