P1250 种树

这道题一开始的思路就是就是差分约束，而遇到差分约束一开始就会想不等式，来解题；

差分约束系统，变量dis[k]是前k家种树的前缀和，满足三个条件：
1.s[e] - s[b-1] >= T （居民要求）
2.s[k] - s[k-1] >= 0 （不能种负树）
3.s[k] - s[k-1] <= 1 （一块地种一棵）

因为求出满足所有要求的最少的树的数量；

所以我们可以按右端排序；

当前区间不满则在右端种树；

这样可以保证重复最多；

这样重复越多就就使剩余树的数量更小；

基本思路是这样的

接下来；

上代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=30005;
 4 struct cs{
 5     int v,to,nxt;
 6 }a[N*100];
 7 int d[N];
 8 bool vis[N];
 9 int head[N],ll;
10 int x,y,n,m,z;
11 void cru(int x,int y,int z)//标准链式存法；
12 {
13     a[++ll].to=y;
14     a[ll].v=z;
15     a[ll].nxt=head[x];
16     head[x]=ll;
17 }
18 void SPFA(int S)//spfa求最小数量树数量；
19 {
20     memset(d,-127,sizeof d);
21     queue<int>Q;
22     Q.push(S);
23     d[S]=0;
24     while(!Q.empty())
25     {
26         int x=Q.front();
27         Q.pop();
28         vis[x]=0;
29         for(int k=head[x];k;k=a[k].nxt)
30         {
31             if(d[a[k].to]<d[x]+a[k].v)
32             {
33                 d[a[k].to]=d[x]+a[k].v;
34                 if(!vis[a[k].to])
35                 {
36                     vis[a[k].to]=1;
37                     Q.push(a[k].to);
38                 }
39             }
40         }
41     }
42 }//标准模板；
43 int main()
44 {
45     scanf("%d%d",&n,&m);
46     while(m--)
47     {
48         scanf("%d%d%d",&x,&y,&z);
49         cru(x-1,y,z);
50     }
51     for(int i=1;i<=n;i++)
52     {
53         cru(i-1,i,0);
54         cru(i,i-1,-1);
55     }//参考大佬和题解的，才面勉强写出；
56     SPFA(0);
57     printf("%d",d[n]);
58 }

其实我差分约束学的不是很好，再此我推荐一篇好的博客：差分约束；

Today is over！！

Keep on going never give up. 　　勇往直前，决不放弃！