西瓜种植

编程入门行业动态更新时间:2024-10-11 05:25:02

西瓜种植

题目描述

笨笨种了一块西瓜地，但这块西瓜地的种植范围是一条直线的……
笨笨在一番研究过后，得出了m个结论，这m个结论可以使他收获的西瓜最多。
笨笨的结论是这样的：
从西瓜地B处到E处至少要种植T个西瓜，这个范围的收获就可以最大化。
笨笨不想那么辛苦，所以他想种植的西瓜尽量少，而又满足每一个所得的结论。

输入

第一行两个数n,m（0<n<=5000,0<=m<=3000），表示笨笨的西瓜地长n，笨笨得出m个结论。
接下来m行表示笨笨的m个结论，每行三个数b,e,t（1<=b<=e<=n,0<=t<=e-b+1）。

输出

输出笨笨最少需种植多少西瓜。

样例输入

9 4
1 4 2
4 6 2
8 9 2
3 5 2

样例输出

提示

基本上来说，笨笨的西瓜地就是一条壮观的线……

Solution

应该可以一眼看出这是差分约束题,那么怎么建边?

对于每个要求,(a,b,c)代表[a,b]区间内至少要种c个西瓜

那么转化为前缀和思想,也就是\(Sum_b-Sum_{a-1}>=c\)

而对于每个点,最少种0个西瓜,最多种1个

那么\(Sum_i-Sum_{i-1}>=0\),\(Sum_i-Sum_{i-1}<=1\),后者转化为\(Sum_{i-1}-Sum_i>=-1\)

注意:建边知道了就没什么了,然后就是千万千万不能用dijkstra,因为有负边权,博主之前调了好久就是没发现错误一度怀疑自己思路又错了,后面上网一搜发现它们用的都是SPFA,恍然大悟

Code

#include<bits/stdc++.h>
#define il inline
#define lol long long
#define Max(a,b) (a)>(b)?(a):(b)
#define Min(a,b) (a)<(b)?(a):(b)
using namespace std;int in(int &ans)
{ans=0; int f=1; char i=getchar();while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();ans*=f;
}const int N=5010,M=3010;
const int inf=2e9;int n,m,cur;
int to[M+3*N],nex[M+3*N],w[M+3*N],head[N];
int vis[N],dis[N];il void add(int a,int b,int c)
{to[++cur]=b,w[cur]=c;nex[cur]=head[a],head[a]=cur;
}void SPFA()
{for(int i=1;i<=n;i++) dis[i]=-inf;queue<int>q; q.push(0);while(!q.empty()) {int u=q.front(); q.pop(); vis[u]=0;for(int i=head[u];i;i=nex[i]) {if(dis[to[i]]<dis[u]+w[i]) {dis[to[i]]=dis[u]+w[i];if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);}}}
}int main()
{in(n),in(m);for(int i=1;i<=m;i++) {int a,b,c;in(a),in(b),in(c);add(a-1,b,c);}for(int i=1;i<=n;i++) add(0,i,0),add(i,i-1,-1),add(i-1,i,0);SPFA();printf("%d\n",dis[n]);
}