October 9, 2019

SYJOJ#646.射击游戏 离散化+DP

小Y是虚拟世界里的狙击手,他有一个非常强大的武器,一枪可以击杀距离他 kkk 范围内的所有敌人,但也会给小Y带来 kkk 的劳累度。 kkk 由小Y决定。 小Y部队里的侦察兵侦测到了有 nnn 个敌方士兵,第 iii 个士兵会在 aia_{i}a ​i ​​ 分钟出现,距离你bib_{i}b ​i ​​ 距离,你需要在 cic_{i}c ​i ​​ 分钟前杀掉他。如果你没杀掉了你就会被杀。 小Y想知道自己消灭所有敌人的最低劳累度

这题其实就是若干条线段然后让你选几个位置把所有线段都砍断,所以选择在哪里下刀就很关键
对于多条线段重叠的情况,由贪心显然应该选择花费最大的切,顺带把花费小的线段一起切掉
因为线段的范围很大但是数量比较少,所以就采用离散化。
这里说下离散化吧就当复习一下:
就当数据比较分散的时候,比如 1 10 20
我们就可以把他视作1 2 3来处理
这样数组就可以开的比较小...
具体方法就是先排序再去重,然后用low_bound函数把原来的数值替换成新数组中的位置

然后转移的顺序要注意,因为k比i大所以要按长度顺序先循环,或者也可以记忆化搜索

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=300+10;
int a[maxn],b[maxn],c[maxn],d[2*maxn];
int f[maxn*2][maxn*2];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		scanf("%d",&n);
		int nu=0;
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&a[i],&b[i],&c[i]);
			nu++;d[nu]=a[i];nu++;d[nu]=b[i];
		}
		//离散化
		sort(d+1,d+nu+1);
		nu=unique(d+1,d+nu+1)-d-1;
		for(int i=1;i<=n;i++){
			a[i]=lower_bound(d+1,d+nu+1,a[i])-d;
			b[i]=lower_bound(d+1,d+nu+1,b[i])-d;	
		}
		memset(f,0x3f,sizeof(f));
		for(int l=1;l<=nu;l++){
			for(int i=1;i<=nu-l+1;i++){
				int j=i+l-1;    //从i到j
				int x=0;
				for(int k=1;k<=n;k++){
					if(a[k]>=i&&b[k]<=j&&c[k]>c[x])
						x=k;                                //找当前可消去的最大值 
				}
				if(!x){
					f[i][j]=0; 
					//printf("^^^^%d %d 0000 \n",i,j);
					continue;
				}
				for(int k=a[x];k<=b[x];k++){
					f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+c[x]);  //在k的位置切一刀 
					//printf("x=%d a[x]=%d b[x]=%d i=%d j=%d %d k=%d\n",x,a[x],b[x],i,j,f[i][j],k); 
				}
			}
		}
		printf("%d\n",f[1][nu]);
	}
	return 0;
}