print node read stream == dig 最优解 get
传送门
先把所有区间按照左端点排序
f[i] 表示区间 0~i 的最优解
- #include < cstdio > #include < iostream > #include < algorithm > #define max(x, y)((x) > (y) ? (x) : (y))
- int n,
- v;
- int f[3000001];
- struct node {
- int x,
- y;
- }
- p[150001];
- inline int read() {
- int x = 0,
- f = 1;
- char ch = getchar();
- for (; ! isdigit(ch); ch = getchar()) if (ch == ' - ') f = -1;
- for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
- return x * f;
- }
- inline bool cmp(node a, node b) {
- return a.x < b.x;
- }
- int main() {
- int i,
- j = 1;
- n = read();
- for (i = 1; i <= n; i++) p[i].x = read(),
- p[i].y = read(),
- v = max(v, p[i].y);
- std: :sort(p + 1, p + n + 1, cmp);
- for (; ! p[j].x; j++) f[p[j].y] = p[j].y + 1;
- for (i = 1; i <= v; i++) {
- f[i] = max(f[i], f[i - 1]);
- for (; p[j].x == i; j++) f[p[j].y] = max(f[p[j].y], f[i - 1] + p[j].y - p[j].x + 1);
- }
- printf("%d\n", f[v]);
- return 0;
- }
[luoguP1868] 饥饿的奶牛(DP)
来源: http://www.bubuko.com/infodetail-2252987.html