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

阶梯教室设备利用"/>

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

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

Description

• 请写一个程序：

  读入所有演讲的起始和终止时间；

  计算最大的可能演讲总时间；

Input

• 第一行包括一个正整数n，n<=10000，为所有的演讲的数目。以下的n行每行含有两个由空格隔开的整数p和k，0<=p< k<=30000。这样的一对整数表示一个演讲由时间p开始到时间k结束。

Output

• 输出唯一的一个整数，为最长的演讲总时间。

Sample Input

121 23 50 46 87 134 69 109 1211 1415 1914 1618 20

Sample Output

16

题解：

• 最长路 / dp。
• 一题用最长路很容易写啊。每相邻两点之间连一条边权为0的边。然后每组关系就从起点向终点连一条权为(终点坐标 - 起点坐标)的边。最后从0开始，开一遍最短路。输出到坐标30000的最长路就行了。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define N 30005
#define inf 0x7fffffff
using namespace std;struct E {int next, to, dis;} e[N * 5];
int m, num, str = inf, end = -inf;
int h[N], dis[N];
bool vis[N];void add(int u, int v, int w)
{e[++num].next = h[u];e[num].to = v;e[num].dis = w;h[u] = num;
}int main()
{cin >> m;for(int i = 1; i <= m; i++){int l, r;cin >> l >> r;add(l, r, r - l);str = min(str, l);end = max(end, r);}for(int i = 0; i < end; i++) add(i, i + 1, 0);queue<int> que;dis[str] = 0, vis[str] = 1, que.push(str);while(que.size()){int now = que.front(); que.pop();for(int i = h[now]; i != 0; i = e[i].next)if(dis[now] + e[i].dis >= dis[e[i].to]){dis[e[i].to] = dis[now] + e[i].dis;if(!vis[e[i].to]) que.push(e[i].to);}}cout << dis[end];return 0;
}

转载于:.html