POJ - 3616
时间: 2023-10-22 18:04:26 浏览: 51
POJ - 3616是一个题目,题目描述如下:
给定一组区间,每个区间有一个权重,要求选择一些区间,使得这些区间的右端点都小于等于k,并且权重之和最大。请问最大的权重和是多少?
解决这个问题的思路是使用动态规划。首先,将区间按照左端点从小到大进行排序。然后,定义一个dp数组,dp[i]表示右端点小于等于i的所有区间所能得到的最大权重。
接下来,遍历每一个区间,对于每个区间i,将dp[i]初始化为区间i的权重。然后,再遍历i之前的每个区间j,如果区间j的右端点小于等于k,并且区间j的权重加上区间i的权重大于dp[i],则更新dp[i]为dp[j]加上区间i的权重。
最后,遍历整个dp数组,找到最大的权重和,即为所求的答案。
下面是具体的代码实现:
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct interval{
int start, end, weight;
};
interval intervals[10005];
int dp[10005];
int n, m, k;
bool compare(interval a, interval b) {
if (a.start == b.start) {
return a.end < b.end;
} else {
return a.start < b.start;
}
}
int main() {
while(~scanf("%d %d %d", &n, &m, &k)) {
memset(dp, 0, sizeof dp);
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &intervals[i].start, &intervals[i].end, &intervals[i].weight);
}
sort(intervals, intervals + m, compare);
for (int i = 0; i < m; i++) {
dp[i] = intervals[i].weight;
for (int j = 0; j < i; j++) {
if (intervals[j].end <= k && dp[j] + intervals[i].weight > dp[i]) {
dp[i] = dp[j] + intervals[i].weight;
}
}
}
int maxWeight = 0;
for (int i = 0; i < m; i++) {
maxWeight = max(maxWeight, dp[i]);
}
printf("%d\n", maxWeight);
}
}
```