差分约束——区间

传送门：区间

思路：

首先就是要找不等式关系

这里使用前缀和的思想对题目里面的关系进行分析。

设前缀和数组s[i],表示前i个数里面被选出来的数的个数，因为数据的范围时0~50000,所以可以将每个数都放大1个位变成1~50001。因为题目要求的是尽量少的数，所以要用最长路来求。

有s[0]=0;

由前缀和的性质可得出以下的关系式

1.s[i]>=s[i-1]                                                      add(i-1,i,0);

2.s[i]-s[i-1]<=1 ==> s[i-1]>= s[i]-1                     add(i,i-1,-1);

3.对于给出的区间[a,b]都必须有s[b]-s[a-1]>=c  add(a-1,b,c);

这里因为一定有答案，所以不用栈。

代码：
 

#include
#include
#include
#include
using namespace std;
typedef long long ll;
int n,m;
const int N=1e5+10,M=3e5+10;
int e[M],ne[M],h[N],w[M],idx;
ll dist[N];
bool st[N];
int q[N];
void add(int a,int b,int c)
{
  e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
bool spfa()
{
    int hh=0,tt=1;
    memset(dist,-0x3f,sizeof dist);
    dist[0]=0;
    st[0]=true;
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q[tt++]=j;
                   if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
 
    }
    return true;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for(int i=1;i<=50001;i++)
    {
        add(i-1,i,0);
        add(i,i-1,-1);
    }
    while(n--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        a++,b++;
        add(a-1,b,c);
    }
    spfa();
    printf("%lld",dist[50001]);
    return 0;
}