POJ-1180 Batch Scheduling （分组求最优值+斜率优化）

题目大意：有n个任务，已知做每件任务所需的时间，并且每件任务都对应一个系数fi。现在，要将这n个任务分成若干个连续的组，每分成一个组的代价是完成这组任务所需的总时间加上一个常数S后再乘以这个区间的系数和。求最小代价。

题目分析：分组求最优值得问题。不过，这道题采用倒推可能要好做一些。定义状态dp(i)表示完成从第 i 个任务到第n个任务需要的最小代价，则状态转移方程为

dp(i)=min(dp(j)+(sumt(i)-sumt(j)+s)*sumf(i)，很显然的要用斜率优化。

代码如下：

# include<iostream>

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define LL long long

const int INF=1<<30;

const int N=10005;

int n,m;

int q[N];

int t[N];

int f[N];

int dp[N];

void read(int &x)

{

    char ch=' ';

    while(ch<'0'||ch>'9')

        ch=getchar();

    x=0;

    while(ch>='0'&&ch<='9'){

        x=x*10+ch-'0';

        ch=getchar();

    }

}

void init()

{

    for(int i=0;i<n;++i){

        read(t[i]);

        read(f[i]);

    }

    t[n]=f[n]=0;

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

        t[i]+=t[i+1];

        f[i]+=f[i+1];

    }

}

double getK(int i,int j)

{

    return (double)(dp[i]-dp[j])/(double)(t[i]-t[j]);

}

int toDp(int i,int j)

{

    return dp[j]+(t[i]-t[j]+m)*f[i];

}

int solve()

{

    int head=0,tail=-1;

    dp[n]=0;

    q[++tail]=n;

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

        while(head+1<=tail&&getK(q[head+1],q[head])<=(double)f[i])

            ++head;

        dp[i]=toDp(i,q[head]);

        while(head+1<=tail&&getK(i,q[tail])<=getK(q[tail],q[tail-1]))

            --tail;

        q[++tail]=i;

    }

    return dp[0];

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        init();

        printf("%d\n",solve());

    }

    return 0;

}