uva 672 - Gangsters(dp)

发布时间:2016-12-7 3:52:00 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"uva 672 - Gangsters(dp)",主要涉及到uva 672 - Gangsters(dp)方面的内容,对于uva 672 - Gangsters(dp)感兴趣的同学可以参考一下。

题目链接:uva 672 - Gangsters 题目大意:给出n,K,T,表示一个酒店将要有n位客人到来,然后给出每个客人的ti,表示在ti时刻第i位客人来到酒店,ti ≤ T;再给出pi,表示第i位客人进入酒店为酒店带来的收益;接着是si,表示第i位客人要进入酒店需要将门开到正好si的大小。酒店的门每时刻可以增加1,减少1或不动,问说酒店的收益最大值。 解题思路:dp[i]表示第i位客人在si的时刻进入酒店的最大收益,现将所有客人按照达到酒店的顺序排序,然后对于每个客人i,考虑dp[j](j<i)最大值,注意这里是第i位客人进入酒店的最大收益,不一定dp[n]就是最优解,所以过程要维护最优解ans。还有注意也许第j为客人进入后,剩余的时间无法让门变成满足i位客人进入的条件时不能考虑,以及第j位客人根本不能进入的情况。 #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 105; struct state { int t, p, s; }g[N]; int n, K, T, dp[N]; bool cmp(const state& a, const state& b) { return a.t < b.t; } void init () { scanf("%d%d%d", &n, &K, &T); for (int i = 1; i <= n; i++) scanf("%d", &g[i].t); for (int i = 1; i <= n; i++) scanf("%d", &g[i].p); for (int i = 1; i <= n; i++) scanf("%d", &g[i].s); sort(g + 1, g + n + 1, cmp); g[0].t = 0; g[0].s = 0; memset(dp, -1, sizeof(dp)); } int solve() { dp[0] = 0; int ans = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] == -1) continue; int u = g[i].t - g[j].t; int l = max(0, g[j].s - u), r = min(K, g[j].s + u); if (g[i].s >= l && g[i].s <= r) { dp[i] = max(dp[i], dp[j] + g[i].p); } } ans = max(dp[i], ans); } return ans; } int main () { int cas; scanf("%d", &cas); while (cas--) { init(); printf("%d\n", solve()); if (cas) printf("\n"); } return 0; }

上一篇:Linux学习记录--文件|目录的默认权限与隐藏权限
下一篇:Bipartite graph/network学习

相关文章

相关评论