原文链接https://www.cnblogs.com/zhouzhendong/p/CF-Gym100543L.html

题目传送门 - CF-Gym100543L

题意

　　$T$ 组数据。

　　有 $n$ 个外星人，第 $i$ 个外星人将在 $a_i$~$b_i$ 这段时间内出现，距离你 $d_i$ 。

　　任何时刻，你可以使用 $R$ 点能量将距离你不超过 $R$ 的所有外星人全部打死。

　　问你最少使用能量才能干掉所有外星人。

　　$n\leq 300,\ \ \ \ 1\leq a_i\leq b_i\leq 10000, \ \ \ \ 1\leq d_i\leq 10000$

题解

　　首先闭着眼睛离散化一下。

　　考虑优先策划打掉距离你最远的外星人。

　　你可以在他出现时间的任意一个时间点里打他。

　　打完他之后，所有出现时间包含你打的时间点的外星人都被顺手打掉了。

　　于是剩下的问题转化成了两个子问题：打掉所有出现、消失时间都早于你打的时间点的外星人；打掉所有出现、消失时间都晚于你打的时间点的外星人。

　　于是我们可以区间dp。

　　建议写记忆化搜索，比较好写。

　　时间复杂度 $O(n^3)$ 。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=605;

int T,n;

struct Alian{

	int L,R,v;

}a[N];

struct Hash_Table{

	int Ha[N],hs;

	void clear(){hs=0;}

	void push(int x){Ha[++hs]=x;}

	void HASH(){

		sort(Ha+1,Ha+hs+1);

		int _hs=1;

		for (int i=2;i<=hs;i++)

			if (Ha[i]!=Ha[i-1])

				Ha[++_hs]=Ha[i];

		hs=_hs;

	}

	int find(int x){return lower_bound(Ha+1,Ha+hs+1,x)-Ha;}

}h;

int dp[N][N];

int solve(int L,int R){

	if (~dp[L][R])

		return dp[L][R];

	int Max=-1;

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

		if (L<=a[i].L&&a[i].R<=R)

			if (Max==-1||a[i].v>a[Max].v)

				Max=i;

	if (!~Max)

		return dp[L][R]=0;

	dp[L][R]=1e9;

	for (int i=a[Max].L;i<=a[Max].R;i++)

		dp[L][R]=min(dp[L][R],a[Max].v+solve(L,i-1)+solve(i+1,R));

	return dp[L][R];

}

int main(){

	scanf("%d",&T);

	while (T--){

		scanf("%d",&n);

		h.clear();

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

			scanf("%d%d%d",&a[i].L,&a[i].R,&a[i].v);

			h.push(a[i].L);

			h.push(a[i].R);

		}

		h.HASH();

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

			a[i].L=h.find(a[i].L);

			a[i].R=h.find(a[i].R);

		}

		memset(dp,-1,sizeof dp);

		printf("%d\n",solve(1,h.hs));

	}

	return 0;

}

巴特西

Codeforces Gym100543L Outer space invaders 区间dp 动态规划

题目传送门 - CF-Gym100543L

题意

题解

代码

最新文章

热门文章