题解 P4360 【[CEOI2004]锯木厂选址】
hicc0305
2018-05-02 11:27:05
一道斜率优化的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;
}
```