找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1573|回复: 0
收起左侧

[米群网刷题小分队] [PAT-TOP] 1002. Business

[复制链接]
发表于 5-2-2015 08:24 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1002 Business
任务安排问题,每个任务有一个需要做的天数,利润,和期限,只有在期限内完成才能得到利润。

我是用背包dp做的,可以证明,按照期限排序的顺序选最好,关键问题是需要的天数不是1,如果都是1,显然可以贪心了。 最痛恨的是这个题数据没给范围,于是dp不敢开数组,只用了map,代码倒是不难写。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <map>
  5. #include <vector>

  6. using namespace std;

  7. struct node {
  8. int p;
  9. int l;
  10. int d;
  11. };

  12. bool cmp(const node &a, const node &b) {
  13.         return a.d < b.d;
  14. }

  15. node a[55];
  16. map<int,int> dp;

  17. int main() {
  18. int n;
  19.         scanf("%d", &n);
  20.         for (int i = 0; i < n; ++i) {
  21.                 scanf("%d%d%d", &a【i】.p, &a【i】.l, &a【i】.d);
  22.         }
  23.         sort(a, a + n, cmp);
  24.         dp[0] = 0;
  25.         int answer = 0;
  26.         for (int i = 0; i < n; ++i) {
  27.                 int x = a【i】.d - a【i】.l;
  28.                 vector<pair<int,int> > may;
  29.                 for (map<int, int>::iterator t = dp.begin(); (t != dp.end()) && (t->first <= x); ++t) {
  30.                         may.push_back(make_pair(t->first + a【i】.l, t->second + a【i】.p));
  31.                 }
  32.                 for (int j = 0; j < may.size(); ++j) {
  33.                         map<int, int>::iterator t = dp.find(may[j].first);
  34.                         if (t == dp.end()) {
  35.                                 dp.insert(may[j]);
  36.                                 answer = max(answer, may[j].second);
  37.                         }
  38.                         else if (t->second < may[j].second) {
  39.                                 answer = max(answer, t->second = may[j].second);
  40.                                
  41.                         }
  42.                        
  43.                 }
  44.         }
  45.         printf("%d\n",answer);
  46.         return 0;
  47. }
复制代码


本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表