铁路建设监理协会网站,导航网,wordpress模板图片路径,开发网页的工具有哪些时间限制#xff1a;1 秒 内存限制#xff1a;32 兆 特殊判题#xff1a;否 提交#xff1a;2046 解决#xff1a;894 题目描述#xff1a;每年毕业的季节都会有大量毕业生发起狂欢#xff0c;好朋友们相约吃散伙饭#xff0c;网络上称为“bg”。参加不同团体的bg会有不… 时间限制1 秒 内存限制32 兆 特殊判题否 提交2046 解决894 题目描述 每年毕业的季节都会有大量毕业生发起狂欢好朋友们相约吃散伙饭网络上称为“bg”。参加不同团体的bg会有不同的感觉我们可以用一个非负整数为每个 bg定义一个“快乐度”。现给定一个bg列表上面列出每个bg的快乐度、持续长度、bg发起人的离校时间请你安排一系列bg的时间使得自己可以获得最 大的快乐度。 例如有4场bg 第1场快乐度为5持续1小时发起人必须在1小时后离开 第2场快乐度为10持续2小时发起人必须在3小时后离开 第3场快乐度为6持续1小时发起人必须在2小时后离开 第4场快乐度为3持续1小时发起人必须在1小时后离开。 则获得最大快乐度的安排应该是先开始第3场获得快乐度6在第1小时结束发起人也来得及离开再开始第2场获得快乐度10在第3小时结束发起人正好来得及离开。此时已经无法再安排其他的bg因为发起人都已经离开了学校。因此获得的最大快乐度为16。 注意bg必须在发起人离开前结束你不可以中途离开一场bg也不可以中途加入一场bg。 又因为你的人缘太好可能有多达30个团体bg你所以你需要写个程序来解决这个时间安排的问题。 输入 测试输入包含若干测试用例。每个测试用例的第1行包含一个整数N (30)随后有N行每行给出一场bg的信息 h l t 其中 h 是快乐度l是持续时间小时t是发起人离校时间。数据保证l不大于t,因为若发起人必须在t小时后离开bg必须在主人离开前结束。 当N为负数时输入结束。 输出 每个测试用例的输出占一行输出最大快乐度。 样例输入 3
6 3 3
3 2 2
4 1 3
4
5 1 1
10 2 3
6 1 2
3 1 1
-1 样例输出 7
16 第一眼的感觉就是这题不是贪心就是DP果然---DP。 DP不熟啊 参考代码http://blog.csdn.net/wtyvhreal/article/details/42076485 //Asimple
#include iostream
#include algorithm
#include cstring
#include cstdio
#include cctype
#include cstdlib
#include stack
#include cmath
#include map
#include string
#include queue
#define INF 100000
using namespace std;
const int maxn 1005;
typedef long long ll;
int m[31][maxn];
int n;
struct bg_typ{int h;int l;int t;bool operator (const bg_typ A) const {return A.t t;}
};
bg_typ bg[31];int main(){while( cin n n 0 ){int mmax 0;for(int i1; in; i){cin bg[i].h bg[i].l bg[i].t ;if( bg[i].t mmax ) mmax bg[i].t; }sort(bg1,bgn1);for(int i0; in; i)m[i][0] m[0][i] 0;for(int i1; in; i){for(int j0; jmmax; j){if( jbg[i].t j-bg[i].l0){m[i][j] max(m[i-1][j],m[i-1][j-bg[i].l]bg[i].h);} else m[i][j] m[i-1][j];}}int resultm[n][mmax]; for(int jmmax;j0;--j)if(resultm[n][j]) resultm[n][j]; coutresultendl; }return 0;
} 翻了翻题解看到有的用dfs也做出来了就测试了下是DP好还是DFS好。 DFS代码 #include cstdio
#include algorithm using namespace std; const int N 30 5; struct Node
{ int h; int l; int t;
}; int n;
Node node[N];
int ans;
int w; bool cmp(const Node a, const Node b); void dfs(int cur, int t, int h); int main()
{ #ifndef ONLINE_JUDGE freopen(e:\\uva_in.txt, r, stdin); #endif // ONLINE_JUDGE while (scanf(%d, n) 1) { if (n 0) break; w 0; for (int i 0; i n; i) { scanf(%d%d%d, node[i].h, node[i].l, node[i].t); w node[i].h; } sort(node, node n, cmp); ans 0; dfs(0, 0, 0); printf(%d\n, ans); } return 0;
} bool cmp(const Node a, const Node b)
{ if (a.t ! b.t) return a.t b.t; return (double)a.h / a.l (double)b.h / b.l;
} void dfs(int cur, int t, int h)
{ if (cur n) { if (ans h) ans h; return; } w - node[cur].h; if (t node[cur].l node[cur].t) { dfs(cur 1, t node[cur].l, h node[cur].h); } if (h w ans) dfs(cur 1, t, h); w node[cur].h;
} 在杭电测试的上面的是动态规划下面的是dfs。 Run IDSubmit TimeJudge StatusPro.IDExe.TimeExe.MemoryCode Len.LanguageAuthor182272612016-09-11 10:40:16Accepted188146MS1928K1480 BCAsimple182272522016-09-11 10:39:32Accepted188162MS1720K1405 BCAsimple各有各的优势吧转载于:https://www.cnblogs.com/Asimple/p/5861206.html
