差分约束裸题。
l-1向r连c的边，i向i+1连0的边，还有i+1向i连-1的边。
//Twenty#include#include #include #include #include #include #include #include typedef long long LL;using namespace std;const int maxn=1005; int ans,n,l,r,x;namespace fastIO { const int sz=1<<15|1; char buf[sz],ch,*l,*r; void gechar(char &c) { if(l==r) r=(l=buf)+fread(buf,1,sz,stdin); c = l==r?(char)EOF:*l++; } template void read(T &x) { int f=1; x=0; gechar(ch); while(ch!='-'&&(ch<'0'||ch>'9')) gechar(ch); if(ch=='-') f=-1,gechar(ch); for(;ch>='0'&&ch<='9';gechar(ch)) x=x*10+ch-'0'; x*=f; }}int ecnt,fir[maxn],nxt[maxn<<2],to[maxn<<2],val[maxn<<2];void add(int u,int v,int w) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w; //nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w;}void init() { fastIO::read(n); for(int i=0;i<1001;i++) add(i,i+1,0),add(i+1,i,1); for(int i=1;i<=n;i++) { fastIO::read(l); l++; fastIO::read(r); r++; fastIO::read(x); add(l-1,r,-x); }}int vis[maxn],dis[maxn];queue que;int spfa(int s) { memset(dis,127,sizeof(dis)); dis[s]=0; que.push(s); while(!que.empty()) { x=que.front(); que.pop(); vis[x]=0; for(int i=fir[x];i;i=nxt[i]) { if(dis[to[i]]>dis[x]+val[i]) { dis[to[i]]=dis[x]+val[i]; if(!vis[to[i]]) { vis[to[i]]=1; que.push(to[i]); } } } } return -dis[1001];}void work() { ans=spfa(0); printf("%d\n",ans);}//#define DEBUGint main() {#ifdef DEBUG freopen("1.in","r",stdin);#endif init(); work(); return 0;}