Codeforces Gym100543L：Outer space invaders（区间DP）

题目链接

题意

有n个人，每个人有一个出现时间a和一个开枪时间b和一个距离d，在任意一个时刻，你可以选择炸人，你要炸一个人的花费是和他的距离d，并且所有的已经出现并且还没开枪的和你距离<=d的人都可以被炸死。问炸死所有人的最小花费是多少。

例如样例就是在第四个时间点炸，这样可以把三个人都炸死。

思路

区间DP。将时间离散化，dp[st][ed]表示炸完在st到ed这段时间的所有人的最小花费是多少。

我们每次都找到只属于当前区间里面的人的花费的最大值。

如果找不到只属于这段区间的点，那么这段区间的花费为0.

否则就从找到的最大花费的这个人的区间左端点开始往右端点扫。代表在这个时间点去炸死这个人。（因为这个人只存活于这个区间，因此要炸死这个人，必须要在这个区间里面炸）。

#include <bits/stdc++.h>

using namespace std;

#define N 605

const int INF = 0x3f3f3f3f;

struct Node {

	int l, r, w;

} p[N];

int dp[N][N], x[N];

int main() {

	int t; scanf("%d", &t);

	while(t--) {

		int n; scanf("%d", &n);

		int m = 0;

		for(int i = 1; i <= n; i++) {

			int l, r, w; scanf("%d%d%d", &l, &r, &w);

			p[i] = (Node) { l, r, w };

			x[++m] = l; x[++m] = r;

		}

		sort(x + 1, x + 1 + m);

		m = unique(x + 1, x + 1 + m) - x - 1;

		for(int i = 1; i <= n; i++) {

			p[i].l = lower_bound(x + 1, x + 1 + m, p[i].l) - x;

			p[i].r = lower_bound(x + 1, x + 1 + m, p[i].r) - x;

		}

	    //	memset(dp, INF, sizeof(dp));

		for(int len = 1; len <= m; len++) { // dp[st][ed] 消掉st到ed这段区间的人的花费

			for(int st = 1; st <= m - len + 1; st++) {

				int ed = st + len - 1, id = 0;

				for(int i = 1; i <= n; i++) // 找出花费最大的人,这个人只能在属于自己的这段区间解决掉

					if(st <= p[i].l && p[i].r <= ed)

						if(id == 0 || p[i].w > p[id].w) id = i;

				if(id == 0) { dp[st][ed] = 0; continue; }

				dp[st][ed] = INF;

				for(int gap = p[id].l; gap <= p[id].r; gap++) // 枚举在哪一点去炸掉这个人最优,因为这个人不能被dp[st][gap-1]到dp[gap+1][ed]的点消除

					dp[st][ed] = min(dp[st][gap-1] + dp[gap+1][ed] + p[id].w, dp[st][ed]);

			}

		}

		//for(int i = 1; i <= m; i++)

		// 	for(int j = i; j <= m; j++)

		//		printf("dp[%d][%d] : %d\n", i, j, dp[i][j]);

		printf("%d\n", dp[1][m]);

	}

	return 0;

}

巴特西

Codeforces Gym100543L：Outer space invaders（区间DP）

题意

思路

最新文章

热门文章