POJ2393 Yogurt factory

贪心 Dp

Vjudge

可以看出，每周的牛奶要么全是本周产出的，要么全是之前某周生产的。而且生产的那周一定是由单调性的，也就是不会一下子第 $i$ 周生产最优后面又变成 $i-k$ 周最优。

那么跑一个 DP ，大概就是设 $f(i)$ 为第 $i$ 周时 “获得” 一单位牛奶的最低价格。那么 $f(i)=\min\{f(i-1)+S,C_i\}$ ，每次再用这个值乘 Y 。前面那个性质就保证了这个 DP 是有最优子结构的。

#include <iostream>
#include <cstdio>
#define int long long
const int MAXN = 10000 + 5;
int N, S, Ans;
int C[MAXN], Y[MAXN], Dp[MAXN];
inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
signed main()
{
    N = read();
    S = read();
    for(int i = 1; i <= N; ++i)
    {
        C[i] = read();
        Y[i] = read();
    }
    Dp[1] = C[1];
    Ans = C[1] * Y[1];
    for(int i = 2; i <= N; ++i)
    {
        Dp[i] = std::min(Dp[i - 1] + S, C[i]);
        Ans += Dp[i] * Y[i];
    }
    printf("%lld\n", Ans);
    return 0;
}