cf864 E. Fire
2022/4/29 6:13:14
本文主要是介绍cf864 E. Fire,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
每个任务有所需时间、DDL、价值。最大化总价值
任务数 <= 100,所需时间 <=20,DDL <= 2000,价值 <= 20
思路:
按DDL从小到大排序,然后做一个正常的01背包
或许跟 gym103640 M. Most Ordered Way 有一点点相似?单线程做任务,都是先做ddl靠前的
const signed N = 103, M = 2003; int n, f[N][M], pre[N][M]; struct node { int t, d, p, id; void rd(int i) { cin >> t >> d >> p, id = i; } } a[N]; vector<int> ve; void dfs(int n, int m) { //回溯路径 if(!n) return; int pm = pre[n][m]; dfs(n-1, pm); if(f[n][m] > f[n-1][pm]) ve.pb(a[n].id); } signed main() { iofast; cin >> n; for(int i = 1; i <= n; i++) a[i].rd(i); sort(a + 1, a + 1 + n, [](const node &a, const node &b) { return a.d < b.d; }); memset(f, -1, sizeof f); f[0][0] = 0; for(int i = 1; i <= n; i++) for(int j = 0; j < a[i].d; j++) { if(~f[i-1][j]) f[i][j] = f[i-1][j], pre[i][j] = j; if(j >= a[i].t && f[i-1][j-a[i].t] + a[i].p > f[i][j]) if(~f[i-1][j-a[i].t]) //要来自合法的状态 f[i][j] = f[i-1][j-a[i].t] + a[i].p, pre[i][j] = j-a[i].t; } int p = max_element(f[n], f[n]+M) - f[n]; cout << f[n][p] << endl; dfs(n, p); cout << ve.size() << endl; for(int i : ve) cout << i << ' '; }
这篇关于cf864 E. Fire的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验
- 2024-05-29AutoMQ 对象存储数据高效组织的秘密: Compaction
- 2024-05-29活动预告|来 GIAC 大会听大数据降本利器:AutoMQ 基于云原生重新设计的 Kafka