首页 > 其他 > 详细

Pearls HDU - 1300 斜率dp

时间:2020-03-17 22:57:54      阅读:49      评论:0      收藏:0      [点我收藏+]

斜率dp优化

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5;
int val[N],sum[N],dp[N];
int q[N],r,l;
int getup(int r,int l) {
    return dp[r]-dp[l];
}
int getdown(int r,int l) {
    return sum[r]-sum[l];
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        int n;
        scanf("%d", &n);
        sum[0]=0;
        for(int i=1; i<=n; i++)
            scanf("%d%d", &sum[i],&val[i]),sum[i]+=sum[i-1];
        l=r=0;
        q[0]=0;
        for(int i=1; i<=n; i++) {
            while(l<r && getup(q[l+1],q[l])<=val[i]*getdown(q[l+1],q[l]))
                l++;
            int j=q[l];
            dp[i]=dp[j]+(sum[i]-sum[j]+10)*val[i];
            while(l<r&&getup(i,q[r-1])*getdown(q[r],q[r-1])<=getup(q[r],q[r-1])*getdown(i,q[r-1]))
                r--;
            q[++r]=i;
        }
        printf("%d\n", dp[n]);
    }
}

直接dp

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int dp[1100];
int a[1100];
int b[1100];
int sum[1100];
int main() {
    int c,n;
    scanf("%d",&c);
    while(c--) {
        scanf("%d",&n);
        sum[0]=0;
        dp[0]=0;
        for(int i=1; i<=n; i++) {
            scanf("%d%d",&a[i],&b[i]);
            sum[i]=sum[i-1]+a[i];///sum数组累计前i种珍珠需要的数量
        }
        for(int i=1; i<=n; i++) {
            dp[i]=dp[i-1]+(a[i]+10)*b[i];///dp[i]表示单一购买时的价格
            for(int j=0; j<i; j++) 
                dp[i]=min(dp[i],dp[j]+(sum[i]-sum[j]+10)*b[i]);///将dp[i]同另一种购买方式比较,取最小的
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

Pearls HDU - 1300 斜率dp

原文:https://www.cnblogs.com/QingyuYYYYY/p/12513760.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!