CF1430F. Realistic Gameplay，动态规划，打僵尸，一个弹夹k发子弹，求最少消耗的子弹。

CF1430F. Realistic Gameplay

题意：

打僵尸游戏，你有一把枪，一个弹夹里装着$k$发子弹，有$n$波僵尸，每一波僵尸在$[l_i,r_i]$时间内同时出现$a_i$个，$n$个区间相互不重合，消灭僵尸不消耗时间，但是换弹夹（将子弹填充满）需要$1$个时间，若换掉的弹夹里还有子弹，则这些子弹被统计为额外的消耗，求的是消灭所有僵尸所消耗的最少的子弹数量（僵尸的数量加上丢掉的子弹数量）是多少（等价于丢掉的子弹的数量最少）？

题解：

首先能想到的DP就是$dp[i][2]$的状态表示，$dp[i][0]$表示消灭了前$i-1$波的僵尸且在第$i$波开始前换弹的丢掉子弹的最小值；$dp[i][1]$表示消灭了前$i-1$波且在第$i$波不换弹的最小值。
但是随即想到这样的状态表示是有问题的，对于$dp[i][1]$的状态来说，因为没有换弹，所以还需要知道在这第$i$波开始时当前弹夹内剩余的子弹是多少，但是这样的状态没法和最小值同时记录，如果将其作为额外的一维状态明显不可能。
但是通过对$dp[i][1]=min(dp[i-1][0],dp[i-1][1])+cost$的转移方程的分析，我们可以发现$dp[i][1]$是由前一个换弹和前一个不换弹这两个状态推过来的，对于$i-1$换弹的状态来说，我们知道它开始时的弹夹是满的，所以也能知道打完第$i-1$波，第$i$波开始的子弹数是多少，同时又因为$dp[i-1][1]=min(dp[i-2][0],dp[i-2][1])$，所以第$i-1$波不换弹的最优解也是由之前的换弹的时候的最优解递推过来得到的。

也就是说，第$i$波开始之前的状态都是由$[1...i-1]$波满子弹的时候递推过来的。但是如果每次都对$[1...i-1]$进行遍历，因为其中的一些状态已经遍历过了，所以对状态表示进行一些优化。

用$dp[i]$表示消灭前$i-1$波僵尸且在第$i$波开始之前装满子弹的状态的最小值。
那么初始状态$dp[0]=0$，最终答案为$dp[n]$。
每一次由$i$往前$i+1$递推到最远处，就能计算出最终答案。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e3 + 10;
int l[N], r[N], a[N];
const ll inf = 1e18;

int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> l[i] >> r[i] >> a[i];
	}
	
	vector<ll> f(n+1, inf);
	f[0] = 0;
	for (int i = 0; i < n; i++) {
		ll now = k;
		ll ans = f[i];
		for (int j = i; j < n; j++) {
		    // 消灭完当前波怪物所换弹必须消耗的时间
			int time = (max(0LL, a[j] - now) + k - 1) / k;
			if (time > r[j]-l[j]) break;
			
			ll newNow = (now + k*time) - a[j];
			ans += a[j];
			
			if (j+1 < n) {
				// 得留有至少1个时间进行换弹
				if (l[j] + time < l[j+1])
					f[j+1] = min(f[j+1], ans + newNow);
			} else {
				f[j+1] = min(f[j+1], ans);
			}
			
			now = newNow;
		}
	}
	
	if (f[n] == inf) {
		cout << -1;
	} else {
		cout << f[n] << endl;
	}
}