首页 > 代码库 > bzoj 3928: [Cerc2014] Outer space invaders
bzoj 3928: [Cerc2014] Outer space invaders
$f[i][j]$表示消灭起始时间在$(i,j)$内的外星人所花费的最小代价。
考虑在这个区间内距离最远的外星人h，在他的区间中一定要选一个点要开一炮，而且这一炮可以顺便把其他跨过这个点的敌人消灭，剩下只需消灭没有跨过这个点的敌人。
枚举开炮时间$f[i][j]=min(f[i][k]+f[k][j]+d[h])$.
区间需要离散化。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define N 605using namespace std;int n;int li[N],cnt;int a[N],b[N],d[N];int f[N][N];int main(){ int cas; scanf("%d",&cas); while(cas--) { scanf("%d",&n);cnt=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&a[i],&b[i],&d[i]); li[++cnt]=a[i];li[++cnt]=b[i]; } sort(li+1,li+cnt+1); cnt=unique(li+1,li+cnt+1)-li-1; for(int i=1;i<=n;i++) { a[i]=lower_bound(li+1,li+cnt+1,a[i])-li; b[i]=lower_bound(li+1,li+cnt+1,b[i])-li; } cnt++; for(int l=0;l<=cnt;l++) { for(int i=0;i<=cnt-l;i++) { int j=i+l;int h=-1; for(int k=1;k<=n;k++) { if(a[k]>i&&b[k]<j) { if(h==-1||d[k]>d[h])h=k; } } if(h==-1)f[i][j]=0; else { f[i][j]=0x3f3f3f3f; for(int k=a[h];k<=b[h];k++) { f[i][j]=min(f[i][j],f[i][k]+f[k][j]+d[h]); } } } } printf("%d\n",f[0][cnt]); } return 0;}
bzoj 3928: [Cerc2014] Outer space invaders
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。