POJ 1260 Pearls （斜率DP）题解

思路：

直接DP也能做，这里用斜率DP。

dp[i] = min{ dp[j] + ( sum[i] - sum[j] + 10 )*pr[i]} ;

k<j<i => dp[j] - dp[k] <pr[i]*( sum[j] - sum[k] ）

再套模板

#include<queue>

#include<cstring>

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<vector>

#include<cstdio>

#include<iostream>

#include<algorithm>

#define ll long long

const int N = 1000+5;

using namespace std;

int pr[N],sum[N],dp[N],q[N];

int up(int x,int y){

	return dp[x] - dp[y];

}

int down(int x,int y){

	return sum[x] - sum[y];

}

int main(){

	int n,m,T;

	scanf("%d",&T);

	while(T--){

		scanf("%d",&n);

		for(int i = 1;i <= n;i++) scanf("%d%d",&sum[i],&pr[i]);

		for(int i = 2;i <= n;i++) sum[i] += sum[i-1];

		int head,tail;

		head = tail = 0;

		dp[0] = 0;

		q[tail++] = 0;

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

			while(head+1 < tail && up(q[head+1],q[head]) <= pr[i]*down(q[head+1],q[head])){

				head++;

			}

			dp[i] = dp[q[head]] + (sum[i] - sum[q[head]] + 10)*pr[i];

			while(head + 1 < tail && up(i,q[tail - 1])*down(q[tail - 1],q[tail - 2]) <= up(q[tail - 1],q[tail - 2])*down(i,q[tail - 1])){

				tail--;

			}

			q[tail++] = i;

		}

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

	}

    return 0;

}

巴特西

POJ 1260 Pearls （斜率DP）题解

最新文章

热门文章