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