CF500C New Year Book Reading 题解

这一题是一道比较复杂的贪心(对于本蒟蒻来说)

假如两本书 \(a\) 和 \(b\)，先看 \(a\) 再看 \(b\)，那么我们开始的时候就把 \(a\) 放在上面。

这样的话，我们看 \(a\) 时就不需要搬动 \(b\)，看 \(b\) 的时候会搬动 \(a\)。

而一开始如果把放在上面，看 \(a\) 的时候需要搬动 \(b\)，看 \(b\) 的时候需要搬动 \(a\) ，就比一开始的 \(a\) 放在上面多搬了。

将两本书推到更多也是同样的道理，先看的书放在上面，后看的书放下面。

看相同的书的时候，需要搬动的时两本书之间的所有书，因此需要倒序枚举之前的书。

最后的代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n, m, w[N], a[N], ans;//n,m,w[]意义请看题目，a[]为要看的书，ans为看所有书需要的最少体力
bool vis[N];//vis数组用来标记
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> w[i];//输入每本书的重量，需要的体力
	for (int i = 1; i <= m; i++)
	{
		cin >> a[i];//输入要看的书
		memset(vis, 0, sizeof(vis));//对于每次阅读书，都要重新统计上面的所有书的总重量
		int sum = 0;
		for (int j = i - 1; j >= 1; j--)//倒序枚举之前看过的书
		{
			if (a[j] == a[i])//如果之前看过，那么a[j]前面的书就不需要搬动
				break;
			if (!vis[a[j]])//重复的书只统计一次重量
			{
				sum += w[a[j]];
				vis[a[j]] = true;//标记这本书已经统计过了，后面不计算重量
			}
		}
		ans += sum;//需要的体力加到总体力里面去
	}
	cout << ans;//输出总体力
	return 0;
}