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

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])就可以了

#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])就可以了

#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;
}