HHS]ONE@Z2VQY)I`I.png)
我们见转换一下模型，把a,b当成x，d当成y，建立平面直角坐标系。首先离散a，b。然后就发现好像可以用区间dp。
f[i][j]表示，处理时间i~j（i，j为离散后的值），需要的最小花费。
那么我们暴力找完全在这个区间里的最高区间（也就是d最大）k。然后枚举k在哪个时间被炸毁。
f[i][j]=min(f[i][j],f[i][h-1]+f[h+1][j]+d[k])(a[k]<=h<=b[k])
解决啦！
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,cnt,a[310],b[310],d[310],p[610],f[610][610];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&d[i]);
p[++cnt]=a[i];p[++cnt]=b[i];
}
sort(p+1,p+cnt+1);
cnt=unique(p+1,p+cnt+1)-p-1;
for (int i=1;i<=n;i++)
{
a[i]=lower_bound(p+1,p+cnt+1,a[i])-p;
b[i]=lower_bound(p+1,p+cnt+1,b[i])-p;
}
memset(f,10,sizeof(f));
for (int i=1;i<=cnt;i++)f[i][i-1]=0;
for (int p=1;p<=cnt;p++)
for (int i=1;i<=cnt-p+1;i++)
{
int j=i+p-1;
int maxh=0,h=0;
for (int k=1;k<=n;k++)
if (a[k]>=i&&b[k]<=j&&d[k]>maxh){maxh=d[k];h=k;}
if (!h) f[i][j]=0;else
{
for (int k=a[h];k<=b[h];k++)
f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+maxh);
}
}
printf("%d\n",f[1][cnt]);
}
评论 (0)
