洛谷2439 [SDOI2005]阶梯教室设备利用

双倍经验：洛谷1868 饥饿的奶牛

题意

从 $N$ 个区间中选取一些不重叠的区间，使得总长度最大。

$N\le 10000 \ \ L,R\le 30000$ 。

题解

用 $f[i]$ 表示前 $i$ 个数选取区间的最大总长度，答案即为 $f[n]$ 。

如果存在一个区间 $[y,x]$ ，那么 $f[x]$ 就可以从 $f[y]$ 转移过来。方程式为：

$$f[x] = \max \begin{cases} f[x-1] \\ f[y]+x-y \ , \ \exists [y,x] \end{cases}$$

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct Edge {
    int next,to;
} edge[10005];
int cnt,head[30005],n,m,a,b,f[30005];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        a=read(); b=read();
        add(b,a);
        m=max(m,b);
    }
    for (int x=1;x<=m;x++)
    {
        f[x]=f[x-1];
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            f[x]=max(f[x],f[y]+x-y);
        }
    }
    return !printf("%d",f[m]);
}

双倍经验

洛谷1868 饥饿的奶牛：两个区间的头尾不能重叠，所以改成 $f[y-1]+x-y+1$ 。