题目大意：
给出 n 个带权区间，选择若⼲区间，覆盖 [1, m]，使得每个位置被覆盖权值和的最⼤值最⼩。
n,m ≤ 2000
知识点： 动态规划
解题思路：
一个关键的结论是：每个点最多被两个区间覆盖。如果某个点被三个区间覆盖，那么总可以找到一个区间，去掉之后可使答案更优。
先将区间按照右端点从左到右排序。
dp(i,j) := 选择第 i 个区间，上一段区间的右端点在坐标 j 或者其左边时的答案。易知 dp(i,j) ≤ dp(i,j-1)，因此可以用一种类似前缀和的手法维护：dp(i,j) = MIN(dp(i,j), dp(i,j-1)).
转移方法可以看看代码。
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2010;
const int INF=0x3f3f3f3f;
struct Interval{
int l,r,w;
bool operator <(const Interval &b)const{
if(r==b.r) return l<b.l;
return r<b.r;
}
}iv[MAXN];
int dp[MAXN][MAXN];
int main(){
iv[0].l=iv[0].r=iv[0].w=0;
int T,n,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&iv[i].l,&iv[i].r,&iv[i].w);
sort(iv+1,iv+n+1);
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++) dp[i][j]=INF;
}
dp[0][0]=0;//初始化
int ans=INF;
for(int i=1;i<=n;i++){
for(int j=i-1;j>=0;j--){
int t1=dp[j][iv[i].l-1];
if(t1==INF) continue;
int val;
if(iv[j].r>=iv[i].l)//区间i,j相互覆盖
val=max(t1,iv[i].w+iv[j].w);
else//没有相互覆盖
val=max(t1,iv[i].w);
dp[i][iv[j].r]=min(dp[i][iv[j].r],val);
if(iv[i].r==m)
ans=min(ans,dp[i][iv[j].r]);
}
for(int j=iv[i].l;j<=iv[i].r;j++)
dp[i][j]=min(dp[i][j],dp[i][j-1]);
}
if(ans==INF) puts("-1");
else
printf("%d\n",ans);
}
return 0;
}
全部评论
(0) 回帖