HDOJ 1300 Pearls 斜率优化dp

原题连接：http://acm.hdu.edu.cn/showproblem.php?pid=1300

题意：

题目太长了。。自己看吧

题解：

看懂题目，就会发现这是个傻逼dp题，斜率优化一下就好

代码：

#include<iostream>

#include<cstring>

#include<vector>

#include<cstdio>

#define MAX_N 500

using namespace std;

typedef long long ll;

ll N;

ll sum[MAX_N];

ll dp[MAX_N];

ll a[MAX_N];

ll p[MAX_N];

double Y(int t){

    return dp[t];

}

double X(int t){

    return sum[t];

}

double Slope(int u,int v) {

    return (Y(u) - Y(v)) / (X(u) - X(v));

}

int que[MAX_N];

int T;

int main() {

    cin.sync_with_stdio(false);

    cin>>T;

    while (T--) {

        cin>>N;

        memset(dp,,sizeof(dp));

        memset(que,,sizeof(que));

        memset(sum,,sizeof(sum));

        for (int i = ; i <= N; i++) {

            cin >> a[i] >> p[i];

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

        }

        int front = , rear = ;

        que[rear++] = ;

        for (int i = ; i <= N; i++) {

            while (rear - front >  && Slope(que[front], que[front + ]) <= p[i])front++;

            int j = que[front];

            dp[i] = dp[j] + (sum[i] - sum[j] + ) * p[i];

            while (rear - front >  && Slope(que[rear - ], que[rear - ]) >= Slope(que[rear - ], i))rear--;

            que[rear++] = i;

        }

        cout << dp[N] << endl;

    }

    return ;

}