把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF1657D For Gamers. By Gamers.

题目大意：你有n种随从可以招募（数量级为3e5），第i种消费ci元，攻击力为di,血量为hi，让后现在有m种怪物（数量级同为3e5），血量为H，攻击力为D，你只能招募一种随从任意数量只，你需要完胜怪物（即自己一个随从不死），求解需要的最小钱数，你最多有C元钱（数量级为1e6），如果不能则输出-1。

解：

看起来有二元其实是一元，因为赢下的条件是ndihi>DH，这里我们把hd看作一个随从的“强度”，那么显然购买n个该随从后的强度就是ndihi，要求的即是买到强度大于等于DH的随从所需要的最小钱数。
由于m的大小是3e5，一开始想用mlogn的二分解法，后来还是理所当然地t了，仔细想想，虽然不同的随从有着性价比之分，但由于它们强度和金钱的关系依然的离散的，所以无法形成一个合理的顺序表。
反过来想，每个随从强度和金钱的关系是离散的，但是总强度和金钱的关系却是连续的，因此我们可以用dp来算出每个金钱数对应的最高能达到的强度，然后二分来求金钱数。
那么怎么求呢？容易想到，对于一个花费c元强度为q的随从来讲，有状态dp[kc]=max(kq,dp[kc])，k的范围是1到C/c，如果把3e5个暴力求出来还是会t的。
但是注意到，如果是同金钱而强度不同的随从，该选择的肯定是强度最高的那个吧，所以每种消费的随从我最多只要一个，这样一来我得到的最坏情况是消费分别为1，2,3，…，3e5的随从们。
靠一个二重循环直接加上去，复杂度为(1+1/2+1/3+…+1/n)，这个复杂度是不是挺熟悉的？正是各种筛法所使用的复杂度，一开始我也不知道是多少，暴力测了一下，当n=1e6的时候复杂度是141e6，这是预处理的时间，而对于每个m我只要二分求解即可。
获取这题可以看作一个只能拿一种东西的背包问题？

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 1000005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(int i=a;i<n;i++)
using namespace std;
ll era[maxn];
int main(){
	int n;
	int C;
	cin >> n >> C;
	inc(i, 0, n) {
		int c;
		ll a, b;
		scanf("%d%lld%lld", &c, &a, &b);
		era[c] = max(era[c], a * b);
	}
	inc(i, 1, C+1) {
		for (int j = i; j <= C; j += i) {
			era[j] = max(era[j], era[i] * (j / i));
		}
	}
	inc(i, 1, C + 1) {
		era[i] = max(era[i], era[i - 1]);
	}
	int m;
	cin >> m;
	while (m--) {
		ll D, H;
		scanf("%lld%lld", &D, &H);
		if (era[C] <= D * H) {
			cout << "-1" << " ";
			continue;
		}
		int ans = C;
		int l = 1, r = C;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (era[mid] > D * H) {
				r = mid - 1;
				ans = min(ans, mid);
			}
			else l = mid + 1;
		}
		cout << ans << " ";
	}
}
/*

*/