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

题目大意：

CF 1625C
题目大意，一条长度为l的路，上面有n个限速排，在最左边开头也就是0的位置必有一个，在限速牌右边到下一个限速牌之前，车辆的速度都不能超过这个牌的限速，然后现在你可以移除最多k个限速牌（不能移除开头的），要求移除这些牌之后通过这条路所需的最短时间。
N<=500,l<=1e5

解：

很容易想到这是一道线性dp的题目，因为对于每个限速牌来讲，当你移除了它，改变的仅仅是它之后的速度，它之前的速度没有受到任何的影响，而路牌之后到下一个路牌之前的速度发生了变化，这个变化是多少呢？是这个路牌的前一个路牌所决定的，但是前一个路牌说不定也被移除了捏，那么记录一下上一个没被移除的路牌是谁不就好了。
设定dp[i][j][k]表示到从左起第k个路牌处移除了i个路牌，且最右边的没被移除的路牌为j时需要花费的时间。
则dp[i][j][k]=dp[i-1][j][k-1]由于可以不移除满k个，答案要取min(dp[i])
复杂度为O（n3）
没错聪明的同学会发现并不是这样的，实际上第三维根本没有必要，实际上起到最关键作用的只有j而已，对于每个i直接推进到最后一个路牌，dp[i][j]表示的就是这一次的最小值，并且遍历时将初始值直接设置为j=i，那么实际上没有移除的状态也被考虑进去了。
答案只需要取dp[k][n+1]就行了。

代码

代码
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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <cstring>
#define ll long long
#define maxn 200005
#define mdl 998244353
using namespace std;
ll	dp[501][501];
int cord[501], spd[501];
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, l, k;
	cin >> n >> l >> k;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> cord[i];
	}
	cord[n + 1] = l;
	for (int i = 1; i <= n; i++) {
		cin >> spd[i];
		
	}
	for (int i = 1; i <= n + 1; i++) {
		ans += spd[i - 1] * (cord[i] - cord[i - 1]);
	}
	ll mx = 0;
	for (int i = 0; i <= k; i++) {
		if (i == 0) {
			for (int j = 2; j <= n + 1; j++) {
				dp[i][j] = dp[i][j - 1] + spd[j - 1] * (cord[j] - cord[j - 1]);
			}
		}
		else {
			dp[i][2] = dp[0][2];
			for (int j = 3; j <= n + 1; j++) {
				dp[i][j] = dp[i][j - 1] + spd[j - 1] * (cord[j] - cord[j - 1]);
				for (int g = 1; g <= i && j - g >= 2; g++) {
					dp[i][j] = min(dp[i][j], dp[i - g][j - g - 1] + spd[j - g - 1] * (cord[j] - cord[j - g - 1]));
				}
				//cout << "dp." << i << "." << j << " = " << dp[i][j] << endl;
			}
		}
		
	}
	cout << dp[k][n+1];
}