| 题目名称 | 2009. [USACO Mar09]餐厅清扫 |
|---|---|
| 输入输出 | cleanup.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 9 |
| 题目来源 |
 cstdio
于2015-07-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：31， 提交：65， 通过率：47.69% | ||||
 ~玖湫~ |
100 | 0.023 s | 0.55 MiB | C++ |
 BaDBoY |
100 | 0.063 s | 0.69 MiB | C++ |
 Sky_miner |
100 | 0.064 s | 1.05 MiB | C++ |
 mikumikumi |
100 | 0.074 s | 1.08 MiB | C++ |
 梦那边的美好ET |
100 | 0.084 s | 1.39 MiB | C++ |
 炎帝 |
100 | 0.085 s | 1.08 MiB | C++ |
 CSU_Turkey |
100 | 0.091 s | 1.08 MiB | C++ |
 FoolMike |
100 | 0.106 s | 4.10 MiB | C++ |
 Hzoi_Mafia |
100 | 0.107 s | 1.38 MiB | C++ |
 xyz117 |
100 | 0.115 s | 0.92 MiB | C++ |
| 关于 餐厅清扫 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
只因pos[2]sb的赋了初值，100变30。
。。。 | ||||
|
我老觉得我第二种写法不太对啊...但为什么还能a...好纠结
CSU_Turkey
2017-09-18 16:24
5楼
| ||||
|
膜拜神犇wmdcstdio，一语道破
其实跳并查集的方法挺好写的…… | ||||
|
有些难优化
| ||||
|
我这种人只会写n^2暴力
| ||||
|
裸DP，记录有1~sqrt(N)个不同数的位置，只用它们更新……
也是简单粗暴…… | ||||
TenderRun
Satoshi
cstdio【题目描述】
很久很久以前，$Farmer John$只会做一种食品；而现在$John$能给他的$N（1<=N<=40000）$只奶牛供应$M（1<=M<=N）$种不同的食品。奶牛们非常挑剔，$i$号奶牛只吃食品$P_i（1<=P_i<=M）$。
每天，奶牛们按编号排队进自助餐厅用餐。不幸的是，这么多各类的食品让清扫工作变得非常复杂。当$John$供应$K$种食品，他之后就需要$K^2$的时间进行清扫。
为了减少清扫的时间，$John$决定把排好队的奶牛划分成若干组。
每一组包含一段连续的奶牛，每一次，只让一组奶牛进入餐厅。
这样，他可以让清扫所需的总用时变得最小。请计算这个最小用时。
【输入格式】
第1行输入$N$和$M$，之后$N$行一行输入一个整数$P_i$。
【输出格式】
输出最小用时。
【样例输入】
13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
【样例输出】
11
【提示】
前4组每组包含1只奶牛，第5组包含两只奶牛，第6组包含5只奶牛，第7、8两组各包含1只奶牛。
【来源】
Paul Christiano, 2007
译者：BirDOR