poj 1260 Pearls 斜率優化dp

這個題目數據量很小，但是滿足斜率優化的條件，可以用斜率優化dp來做。

        要注意的地方，0也是一個決策點。

#include <iostream>

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e2+9;
int dp[maxn];
int a[maxn],p[maxn],sum[maxn];
int que[maxn];


bool chk1(int i,int j,int k)
{
    return dp[j]-dp[i]<p[k]*(sum[j]-sum[i]);
}


bool chk2(int k,int j,int i)
{
    return (dp[i]-dp[j])*(sum[j]-sum[k])<(dp[j]-dp[k])*(sum[i]-sum[j]);
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(dp,50,sizeof(dp));
        sum[0]=0;
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d",&a[i],&p[i]);
            sum[i]=sum[i-1]+a[i];
        }
        dp[0]=0;
        int front=1,end=0;
        que[++end]=0;
        for(int i=1;i<=n;i++)
        {
            while(front+1<=end&&chk1(que[front],que[front+1],i))
            front++;
            int j=que[front];
            dp[i]=dp[j]+(sum[i]-sum[j]+10)*p[i];
            while(front+1<=end&&chk2(que[end-1],que[end],i))
            end--;
            que[++end]=i;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}