poj 1180 斜率优化dp

这个题目要是顺着dp的话很难做，但是倒着推就很容易退出比较简单的关系式了。

dp[i]=min(dp[u]+(sum[u-1]-sum[i-1]+s)*f[i]);dp[i]代表从i到结尾需要花费的代价，sum[i]表示1到i的时间和，f[i]代表i到n的代价和。

然后对于i状态来说，j由于k等价于 (dp[j]-dp[k])/(sum[k-1]-sum[j-1])<f[i]

然后f[i]随着i递减而递增，所以就可以利用斜率优化的办法来搞了。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn=1e4+9;

long long sum[maxn],f[maxn];

long long dp[maxn];

int que[maxn];

bool chk1(int k,int j,int i)

{

    return (dp[j]-dp[k])<f[i]*(sum[k-1]-sum[j-1]);

}

bool chk2(int k,int j,int i)

{

    return ((dp[j]-dp[k])*(sum[j-1]-sum[i-1]))>((dp[i]-dp[j])*(sum[k-1]-sum[j-1]));

}

int main()

{

    int n,s;

    while(scanf("%d %d",&n,&s)!=EOF)

    {

        sum[0]=0;

        for(int i=1;i<=n;i++)

        {

            scanf("%lld %lld",&sum[i],&f[i]);

            sum[i]+=sum[i-1];

        }

        for(int i=n-1;i>=1;i--) f[i]+=f[i+1];

        int front=1,end=0;

        que[++end]=n+1;

        dp[n+1]=0;

        for(int i=n;i>=1;i--)

        {

            while(front<end&&chk1(que[front],que[front+1],i))

            front++;

            int u=que[front];

            dp[i]=dp[u]+(sum[u-1]-sum[i-1]+s)*f[i];

            while(front<end&&chk2(que[end-1],que[end],i))

            end--;

            que[++end]=i;

        }

        printf("%lld\n",dp[1]);

    }

    return 0;

}

巴特西

poj 1180 斜率优化dp

最新文章

热门文章