这道题很明显没有紫题难度,不过白水一道紫题还是很香的。
思路:完全背包
对于每一个房间及房间里的钻石,都进行一次完全背包DP。
一些细节:
-
对于每一个房间,其可装最大值不是房间关闭的时间,而是在其之前全部房间内的最早关闭时间。如果超过了这个时间,那么小偷就到不了当前这个房间。
-
最后的答案要从1开始到最大房间的结束时间扫一遍\(f[N]\)数组,取最大值即可。
AC Code:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#define N 105
#define M 1005
using namespace std;
int n, m, f[M], close[N];
struct dimond{
int v[M], w[M], top, last;
}a[55];
int main(){
int fang, vi, wi, minn=1e9, maxn=0, ans=0;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
a[i].top=0;//预处理top为0
scanf("%d", &close[i]);//每一扇房门关闭的时间
minn=min(minn, close[i]);
close[i]=minn;
maxn=max(maxn, close[i]);
}
for(int i=1; i<=m; i++){
scanf("%d%d%d", &fang, &vi, &wi);
fang++;
a[fang].top++;
a[fang].v[a[fang].top]=vi;
a[fang].w[a[fang].top]=wi;
//将宝石加入房间内的队列里
}
for(int i=n; i>0; i--){//每一个房间
for(int j=1; j<=a[i].top; j++){
for(int k=a[i].w[j]; k<close[i]; k++){
f[k]=max(f[k], f[k-a[i].w[j]]+a[i].v[j]);
}
}
}
for(int i=1; i<=maxn; i++) ans=max(ans, f[i]);
printf("%d", ans);
return 0;
}