icpc:problems:luogup1233
problems | |
---|---|
名称 | Sleeping in Class B |
题目编号 | USACO22FEB_B1 |
题目链接 | luogu.com.cn/… |
来源 | USACO |
算法分类 | 枚举, 入门_循环 |
难易程度 | 容易 |
这是本文档旧的修订版!
problems | |
---|---|
名称 | 木棍加工 |
题目编号 | P1233 |
题目链接 | luogu.com.cn/… |
来源 | Luogu |
算法分类 | 动态规划, 线性动态规划 |
难易程度 | 容易 |
木棍加工
想法
做一次最长不上升子序列,该序列中的每一个元素都是一个独立的可不休息的序列。
代码实现
#include<cstdio> #include<algorithm> using namespace std; struct node{ int l, w; }; bool cmp(node a, node b) { return a.l < b.l || (a.l == b.l && a.w < b.w); } const int N = 5010; node line[N]; int f[N]; int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d %d", &line[i].l, &line[i].w); sort(line+1, line+1+n, cmp); for(int i=1; i<=n; i++) { for(int j=i-1; j>=1; j--) if(line[j].w > line[i].w) f[i] = max(f[i], f[j] + 1); } int ans = 0; for(int i=1; i<=n; i++) ans = max(ans, f[i]); printf("%d", ans+1); return 0; }
/app/www/public/data/attic/icpc/problems/luogup1233.1711421493.txt.gz · 最后更改: 2024/03/26 02:51 由 温婕莺