J题
题目大意
给出n个区间，每个区间有一个l, r, w,代表区间左端点，右端点和区间的权值，现在可以选取一些区间，要求选择的区间不相交，问最大的权和可以是多少，如果权和相同，则选区间长度最短的。要求输出区间个数，总权值，总的区间长度和选了哪些区间。
分析
根据最基本的贪心原理可以得到要得到最多的分数，要尽可能的选择结束时间早的（也就是右端点小的排在前面），如果结束时间相同的话就把开始时间早的排在前面。初始化每个区间的dp，len，tol,pre,vis为上一个区间的值，找到满足条件的最近的一个区间，看权和是否变大，或者相等的时候时间是否更小，如果满足条件就更新。这道题就大的看点就是找到是哪几个区间，因为用pre数组记录路径，但是路径只是代表当前的解从哪里更新过来的，而不能记录是由哪一个点推出新的最优解，所以就用via来代表当前这个解最后使用了哪一个区间推出来。pre数组也使用递推的形式。。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 200010
#define INF 0x3f3f3f3f
struct node {
int l, r, w, id;//开始时间，结束时间，得分，序号
bool operator < (const node &rhs) const
{
if(r != rhs.r)
return r < rhs.r;//以右端点来进行排序
return l < rhs.l;//如果结束时间相同就以开始时间早的来排序
}
} p[N];
LL dp[N], len[N];
int tol[N], pre[N], vis[N];
vector<int> ans;
//这里的每个数组可以近似的理解为前缀和，但中间又空缺了某些下标
// vis表示新的DP答案由哪个推出来的
// pre表示当前这个点可以由哪一个点跳过来
//用pre数组来记录路径
// dp[i]表示到第i个右端点的时候最大权和
// len[i]表示到第i个右端点的时候最小长度
// tol[i]表示区间个数
int main() {
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d%d%d", &p[i].l, &p[i].r, &p[i].w);
p[i].id = i;
}
sort(p + 1, p + 1 + n);//排序，数组P的首下标是从1开始的
for(int i = 1; i <=n; i++)
{
dp[i] = dp[i-1], len[i] = len[i-1]; //不断的更新
tol[i] = tol[i-1], pre[i] = pre[i-1], vis[i] = vis[i-1];
//每次循环至少要保存上一次的结果，根据条件来判断是否更新
node now = (node) { INF, p[i].l, 0, 0 };
//定义一个新的结构体变量
int index = upper_bound(p + 1, p + n + 1, now) -p-1;
//找到最接近当前循环区间并且满足条件的区间，越往后dp越大
if(dp[index] + p[i].w > dp[i])
{
dp[i] = dp[index] + p[i].w;
len[i] = len[index] + p[i].r - p[i].l;
tol[i] = tol[index] + 1;
pre[i] = index; vis[i] = i;
}
else if(dp[index] + p[i].w == dp[i]
&& len[index] + p[i].r - p[i].l < len[i])
{
len[i] = len[index] + p[i].r - p[i].l;
tol[i] = tol[index] + 1;
pre[i] = index; vis[i] = i;
//存储加入新DP的数组下标
//pre表示当前这个点可以由哪一个点跳过来
}
}
for(int i=1;i<=n;i++)
printf("%d ",pre[i]);
printf("\n");
for(int i=1;i<=n;i++)
printf("%d ",vis[i]);
printf("\n");
int ed =n;
while(ed)
{
ans.push_back(p[vis[ed]].id);
ed = pre[ed];
}
sort(ans.begin(), ans.end());
printf("%d %lld %lld\n", tol[n], dp[n], len[n]);
for(int i = 0; i < ans.size(); i++)
printf("%d ", ans[i]);
return 0;
}
总结
这道题用到的一些思路非常的新颖，用数组来存储每一个区间的情况，然后不断的更新。
