题目描述
【题意】
给出n个区间，每个整数区间[ai,bi]中至少有ci个点。求整个区间中最少的点数。
【输入格式】
第一行：一个整数n，(1<=n<=50000)。
接下来n行每行三个整数ai，bi，ci，（0<=ai<=bi<=50000），（1<=ci<=bi-ai+1）。
【输出格式】
一个整数Z，表示整个区间中最少有多少个点。
【样例输入】
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
【样例输出】
6
话说差分约束系统以前就学过了。。
然而好像又忘得差不多。。
这题一眼就是统计前缀和，然后差分嘛
这题由于ai,bi的下界都是0，直接差分不方便，于是默认帮他ai++,bi++
推一下柿子:
f[bi]-f[ai]>=ci
f[bi]>=f[ai]+ci
然后对于相邻的两项
0<=f[x+1]-f[x]
f[x+1]>=f[x]+0
f[x]-f[x+1]>=-1
f[x]>=f[x+1]-1
于是跑最长路。。
于是最长路写挫了N发。。
最近不知道在干什么。。
于是感觉这题奥妙重重。。。。。
抄了一下fyc大佬的建图，后来发现最长路写挫了
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=50005;
struct qq
{int x,y,z,last;
}s[N*10];int num,last[N];
void init (int x,int y,int z)
{num++;s[num].x=x;s[num].y=y;s[num].z=z;s[num].last=last[x];last[x]=num;
}
int f[N];
int n,nn=0;
bool in[N];
void SPFA ()
{queue<int> q;memset(in,true,sizeof(in));memset(f,-63,sizeof(f));for (int u=0;u<=nn;u++) q.push(u);f[0]=0;in[0]=true;while (!q.empty()){int x=q.front();q.pop();for (int u=last[x];u!=-1;u=s[u].last){int y=s[u].y;if (f[y]<f[x]+s[u].z){f[y]=f[x]+s[u].z;if (in[y]==false){in[y]=true;q.push(y);}}}in[x]=false;}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d",&n);for (int u=1;u<=n;u++){int x,y,z;scanf("%d%d%d",&x,&y,&z);x++;y++;init(x-1,y,z);nn=max(nn,y);}for (int u=0;u<nn;u++){init(u+1,u,-1);init(u,u+1,0);}SPFA();printf("%d\n",f[nn]);return 0;
}