P4087 [USACO17DEC]Milk Measurement

这是一道USACO的题目，需要模拟题意并进行计算。题目大意是给定一组牛奶产量的记录，每条记录包含三个信息：日期、产奶的牛编号、产奶量。要求统计在某个日期时，产奶量最大的三头牛的编号，如果有多个牛的产奶量同时为第三大，则也要统计在内。

我们可以使用一个哈希表来存储每头牛在每个日期的产奶量，然后按照日期顺序依次处理每条记录，更新每头牛在该日期的产奶量，并统计出该日期产奶量最大的三头牛的编号。对于每个日期，如果产奶量最大的三头牛有变化，则更新计数器。

具体实现细节可以参考下面的代码：

相关问题

P4087 [USACO17DEC]Milk Measurementc++代码

以下是P4087 [USACO17DEC]Milk Measurement的c++代码：

#include<bits/stdc++.h>
using namespace std;
int n,d,i,x,minn=1e9,maxn=-1e9,sum=7;//注意sum要初始化为7，因为一开始有三个人挤奶！
map<int,int> mp;
struct node{
    int day,milk,id;//day表示某一天，milk表示这一天的产奶量，id表示这头牛的编号
}a[100010];
bool cmp(node x,node y){
    return x.day<y.day;
}
int main(){
    scanf("%d%d",&n,&d);
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].day,&a[i].id,&a[i].milk);
        minn=min(minn,a[i].id);//记录最小的牛的编号
        maxn=max(maxn,a[i].id);//记录最大的牛的编号
    }
    sort(a+1,a+n+1,cmp);//排序
    for(i=1;i<=n;i++){
        int p=a[i].id;
        mp[p]+=a[i].milk;//记录每头牛产奶总量
        if(mp[p]-a[i].milk>=mp[minn]&&mp[p]>=mp[minn]){//如果这头牛的产奶总量减去这一天的产奶量后等于最小产奶量且这头牛的产奶总量大于等于最小产奶量
            sum--;
        }
        if(mp[p]>=mp[maxn]&&mp[p]-a[i].milk<mp[maxn]){//如果这头牛的产奶总量大于等于最大产奶量且这头牛的产奶总量减去这一天的产奶量小于最大产奶量
            sum++;
        }
        if(mp[p]-a[i].milk<mp[maxn]&&mp[p]>=mp[maxn]){//如果这头牛的产奶总量减去这一天的产奶量小于最大产奶量且这头牛的产奶总量大于等于最大产奶量
            if(mp[maxn]-mp[p]+a[i].milk>0)sum++;
        }
        mp[p]-=a[i].milk;//减去这一天的产奶量
        if(i==n||a[i].day!=a[i+1].day){//如果到了新的一天或者到了最后一天
            if(mp[maxn]!=mp[a[i].id]&&mp[a[i].id]>=mp[maxn])sum++;//如果这头牛的产奶总量不等于最大产奶量且这头牛的产奶总量大于等于最大产奶量
            if(mp[maxn]==mp[a[i].id]){//如果这头牛的产奶总量等于最大产奶量
                if(a[i].id==maxn)sum+=0;//如果这头牛就是最大产奶量的牛，那么不需要增加计数器
                else sum++;//否则需要增加计数器
            }
            if(mp[minn]!=mp[a[i].id]&&mp[a[i].id]>=mp[minn])sum++;//如果这头牛的产奶总量不等于最小产奶量且这头牛的产奶总量大于等于最小产奶量
            if(mp[minn]==mp[a[i].id]){
                if(a[i].id==minn)sum+=0;//如果这头牛就是最小产奶量的牛，那么不需要增加计数器
                else sum++;//否则需要增加计数器
            }
        }
    }
    printf("%d\n",sum);
    return 0;
}

该题的解题思路是模拟，需要注意细节问题。我们可以首先将输入的数据按天数排序，然后模拟每一天挤奶的情况，并根据题目要求进行计数即可。具体细节请见代码注释。

p2676 [usaco07dec]bookshelf b

题目描述

有一个长度为 $n$ 的书架，每本书有一个高度 $h_i$。现在你可以进行以下两种操作：

- 将一本书放在书架的最左边或最右边，花费为 $c_1$。
- 将一本高度为 $h_i$ 的书放在一本高度为 $h_j$ 的书的上面，花费为 $c_2$。

现在你需要将书架上的书按照高度从小到大排列，求最小花费。

输入格式

第一行包含三个整数 $n,c_1,c_2$。

第二行包含 $n$ 个整数 $h_i$。

输出格式

输出一个整数，表示最小花费。

数据范围

$1\leq n\leq 200,1\leq c_1,c_2\leq 10^9,1\leq h_i\leq 10^9$

输入样例

5 1 2
3 1 4 2 5

输出样例

6

算法1

(动态规划) $O(n^2)$

首先考虑一个朴素的 dp，设 $f_{i,j}$ 表示前 $i$ 本书已经排好序，第 $i+1$ 本书放在第 $j$ 个位置的最小花费。

状态转移方程为：

$$
f_{i,j}=\min\{f_{i-1,k}+c_1\}+\begin{cases}&\text{if }h_{i+1}>h_j\\c_2&\text{otherwise}\end{cases}
$$

其中 $k$ 取遍 $1\sim i$，表示将第 $i+1$ 本书放在第 $k$ 个位置。

时间复杂度

$O(n^3)$

C++ 代码

算法2

(单调队列优化) $O(n^2)$

考虑优化上述 dp，发现状态转移方程中的 $\min$ 操作可以用单调队列优化，具体来说，我们维护一个单调递增的队列 $q$，其中 $q_i$ 表示第 $i$ 个位置的最小花费，那么对于状态 $f_{i,j}$，我们只需要找到 $q$ 中第一个大于等于 $f_{i-1,k}+c_1$ 的位置 $p$，然后 $f_{i,j}=q_p+\begin{cases}&\text{if }h_{i+1}>h_j\\c_2&\text{otherwise}\end{cases}$。

时间复杂度

$O(n^2)$

C++ 代码