3
7
2016
0

[BZOJ3928&4048] [Cerc2014] Outer space invaders

区间DP

离散化后考虑一段区间(l,r)(这里指的是出现时间的区间)

那么这段区间的R的最小值至少为这一段区间最高的线段(感觉讲的很抽象啊……最高的线段高度等于这个外星人离你的距离)

然后输出(0,tb)表示在[1,tb-1]能取到的最小代价,所以中间那个tb要++,因为我用的是开区间

#include<cstdio>
#include<algorithm>
using namespace std;

int n,table[10005],tb,f[1005][1005],T;

struct Plane{
int a,b,d;
}p[305];

int main(){
freopen("3928_4048.in","r",stdin);
freopen("3928_4048.out","w",stdout);
scanf("%d",&T);
while(T--){
    tb=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&p[i].a,&p[i].b,&p[i].d);
        table[++tb]=p[i].a;
        table[++tb]=p[i].b;
    }
    sort(table+1,table+tb+1);
    tb=unique(table+1,table+tb+1)-table-1;
    for(int i=1;i<=n;i++){
        p[i].a=lower_bound(table+1,table+tb+1,p[i].a)-table;
        p[i].b=lower_bound(table+1,table+tb+1,p[i].b)-table;
    }
    tb++;
    for(int len=0;len<=tb;len++){
        for(int i=0;i<=tb-len;i++){
            int j=i+len,H=-1;
            for(int k=1;k<=n;k++){
                if(i<p[k].a && p[k].b<j && (H==-1 || p[H].d<p[k].d))H=k;
            }
            if(H==-1)f[i][j]=0;
            else {
                f[i][j]=2100000000;
                for(int k=p[H].a;k<=p[H].b;k++){
                    f[i][j]=min(f[i][j],f[i][k]+f[k][j]+p[H].d);
                }
            }
        }
    }
    printf("%d\n",f[0][tb]);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 516

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com