首页 > 其他 > 详细

poj 2393 Yogurt factory(贪心)

时间:2018-10-18 20:45:23      阅读:167      评论:0      收藏:0      [点我收藏+]

传送门

解题思路

对于第\(i\)周来说,最小的花费 \(sum=min(y[i]*(c[j]+s(i-j)))(1<=j<=i)\),所以\(sum=min(y[i]*(c[j]-s[j]+s[i])\),发现\(y[i]\)\(s[i]\)均为定值,就是让最小化\(c[j]-s[j]\),然后就直接维护个最小值每次更新答案即可。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define int long long

using namespace std;
const int MAXN = 10005;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch==‘-‘?0:1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();}
    return f?x:-x;
}

int n,s,ans;

signed main(){
    n=rd();s=rd();int mn=1e9;
    for(int i=1;i<=n;i++){
        mn=min(mn,rd()-s*i);
        ans+=rd()*(s*i+mn);
    }cout<<ans;
    return 0;
}

poj 2393 Yogurt factory(贪心)

原文:https://www.cnblogs.com/sdfzsyq/p/9812936.html

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