有n个激光塔排成一行，第i个激光塔的位置为ai，威力是bi，当第i个激光塔被激活后，所有在这个激光塔左边且与该激光塔距离小于等于bi的激光塔都会被摧毁，而该激光塔本身不会受到伤害。管理员从右向左依次激活每个激光塔，如果一个激光塔被摧毁了，则它无法被激活。 现在管理员想让你帮他一个忙，管理员决定在现有的n个激光塔的右边再放一个激光塔，这个激光塔的位置和威力是任意的（但必须在现有激光塔的右边）。管理员从这个新加入的激光塔开始从右到左依次激活每个激光塔，现在他想要知道，怎么安排这个新激光塔，可以使得被摧毁的激光塔的总数最少。
题解：dp
dp[i][0] 表示位置i灯塔不摧毁
dp[i][1] 表示位置i当前灯塔摧毁
所以转移方程为
dp[i][1] = dp[i - 1][0] + 1
dp[i][0] = dp[i - b[i] - 1][0] + sum[i - 1] - sum[i - b[i] - 1]
(sum[i]表示前缀激光灯的数量)
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; const int maxm = 1e6+1; int a[maxn]; int dp[maxn][2]; int sum[maxn]; int main() { int n; int t1, t2; cin >> n; for (int i = 1; i <= n; i++) { cin >> t1 >> t2; t1++; a[t1] = t2; } for (int i = 1; i <= maxm; i++) sum[i] = sum[i - 1] + (a[i] != 0); for (int i = 1; i <= maxm; i++) { dp[i][0] = dp[i - 1][0]; dp[i][1] = dp[i - 1][1]; if (a[i]) { //dp[i][0] 表示当前灯塔不摧毁 //dp[i][1] 表示当前灯塔摧毁 //dp[i][1] = dp[i - 1][0] + 1;(如果当前激光灯已经被摧毁，则下一个激光灯一定是激活激活状态 // cout << i << " " << i - a[i] - 1 << " " << sum[i - 1] - sum[i - a[i] - 1] <<endl; if (i - a[i] > 0) { dp[i][0] = dp[i - a[i] - 1][0] + sum[i - 1] - sum[i - a[i] - 1]; } else { dp[i][0] = sum[i - 1]; } } // cout << i << " "; cout << dp[i][0] << " " << dp[i][1] << endl; } int ans = 1e9; for (int i = 1; i <= maxm; i++) { int t = sum[i]; ans = min(ans, min(dp[i][0], dp[i][1]) + n - t); } cout << ans << endl; return 0; }
