题解 AT4285 【[ABC116D] Various Sushi】
<![CDATA[
### Explanation
有 $N$ 个寿司，选 $K$ 个使得满足最大值。
### Solution
#### Solution 1
$N$ 个选 $K$ 个，乍一看就觉得是背包 DP。
按照背包 DP 解法，
用 $f[i]$ 表示在这 $N$ 个寿司选 $i$ 个寿司所产生的最大满足。
一开始先对所有寿司按照类型排个序，以便于算种类数。
然后按照每个物品的重量为 $1$ 直接往上套 01DP 模板、特判一下寿司种类即可。
由于会爆 $int$，记得开 $long \ long$
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n, k, f[100005], val[100005];
struct node
{
long long t, d;
bool operator<(const node &x) const
{
if (t == x.t)
return d > x.d;
return t < x.t;
}
} a[100005];
int main()
{
scanf("%lld%lld", &n, &k);
for (int i(1); i <= n; ++i)
scanf("%lld%lld", &a[i].t, &a[i].d);
sort(a + 1, a + n + 1);
for (int i(1); i <= n; ++i)
{
if (a[i].t != a[i - 1].t) //特判寿司种类
for (int j(k); j; --j)
{
if (f[j - 1] + a[i].d + (val[j - 1] + 1) * (val[j - 1] + 1) - (val[j - 1] * val[j - 1]) > f[j]) //dp
f[j] = f[j - 1] + a[i].d + (val[j - 1] + 1) * (val[j - 1] + 1) - (val[j - 1] * val[j - 1]), val[j] = val[j - 1] + 1;
}
else
for (int j(k); j; --j)
{
if (f[j - 1] + a[i].d > f[j]) //dp
f[j] = f[j - 1] + a[i].d, val[j] = val[j - 1];
}
}
printf("%lld\n", f[k]);
return 0;
}
```
然后因为 $N \leq 10 ^ 5$，所以我们的 $O(n ^ 2)$ 成功地 T 飞了 /kk
#### Solution 2
考虑一下我们的 DP 哪里最耗时间。
对于某些寿司，加到已经有的寿司队列里不会对寿司种类数产生影响，并且他的价值比队列里的所有寿司都低。
所以对于这种寿司，我们要坚决阻止。
所以我们**小小贪心一下，先挑出来 $k$ 个价值最高的寿司，然后去判寿司种类对结果产生的影响**
好的我们开始。
1. 找出来前 $k$ 个价值最高的寿司
这里我们可以用一个优先队列来找出这些寿司。
在部分代码环节，我们不妨用 $tmp$ 来表示寿司。
用 $q$ 大根堆存储所有寿司，用 $rev$ 小根堆存储 $k$ 个寿司，以备后用
伪代码如下
```
struct Sushi
{
long long t,d;
bool operator<(const node &x) const
return d < x.d;
} tmp;
priority_queue<Sushi> q;
priority_queue<Sushi, vector<Sushi>, greater<Sushi> > rev;
while (input tmp)
q.push(tmp)
for i from 1 to k
rev.push(q.top())
q.pop()
```
2. 在存 $k$ 个寿司的同时，记录一下目前寿司的种类和总满足
由于 $1 \leq t_i \leq N$ 所以这里我用一个 $num$ 数组来记录每中寿司 $t$ 的数量，用一个 $cnt$ 记录总的寿司种类数，用 $sum$ 记录一下总满足
伪代码如下
```
while rev.push(q.top())
if num[q.top().t] == 0
cnt++
num[q.top().t]++
sum += q.top().d
```
3. 计算一下当前的总满足
这里我用一个 $ans$ 记录
伪代码如下
```
ans = sum + cnt * cnt
```
4. 开始判断寿司种类
首先什么样的寿司对我们的答案可能有贡献呢？
##### 这个寿司带来的 “多样性加成” 的收益大于 “基础美味程度总和” 的损失。
所以我们的目标就很明确了。
对于带不来 “多样性加成” 的寿司，我们直接扔掉。
对于带的来 “多样性加成” 的寿司，我们去找到现有的 $k$ 个寿司中 **去掉不会对现有种类造成影响且价值最小的** 寿司，将两寿司交换。
伪代码如下
```
while q.size() && rev.size()
if num[q.top().t] != 0 // 寿司没有带来 “多样性加成”，不能要，去掉
q.pop()
continue
if num[rev.top().t] == 1 // 去掉该寿司会对现有种类造成影响，不能去，找当前的下一个寿司
rev.pop()
continue
// 这样可以找到符合要求的两个寿司交换
```
找到了以后，我们进行交换，计算交换后是否满足
>_这个寿司带来的 “多样性加成” 的收益大于 “基础美味程度总和” 的损失。_
且计算新的总满足，和原来的比较。
伪代码如下
```
num[rev.top().t] --
num[q.top().t] ++
cnt ++
sum -= rev.top().d
sum += q.top().d
ans = max (ans, sum + cnt * cnt)
```
最终找到最大的总满足，得到正解。
### AC Code
```cpp
#include <bits/stdc++.h>
using namespace std;
long long n, k, ans, cnt, num[100005], sum;
struct node
{
long long t, d;
bool operator<(const node &x) const
{ return d < x.d; }
bool operator>(const node &x) const
{ return d > x.d; }
} tmp;
priority_queue<node> q;
priority_queue<node, vector<node>, greater<node>> rev;
int main()
{
scanf("%lld%lld", &n, &k);
for (int i(1); i <= n; ++i)
{
scanf("%lld%lld", &tmp.t, &tmp.d);
q.push(tmp);
}
for (int i(1); i <= k; ++i)
{
if (num[q.top().t]++ == 0)
cnt++;
sum += q.top().d;
rev.push(q.top());
q.pop();
}
ans = sum + cnt * cnt;
while (q.size() && rev.size())
{
if (num[q.top().t] != 0)
{
q.pop();
continue;
}
if (num[rev.top().t] == 1)
{
rev.pop();
continue;
}
num[rev.top().t]--;
num[q.top().t]++;
cnt++;
sum -= rev.top().d;
sum += q.top().d;
rev.pop();
q.pop();
ans = sum + cnt * cnt > ans ? sum + cnt * cnt : ans;
}
printf("%lld\n", ans);
return 0;
}
```
]]>