Hatena::Grouptopcoder

peryaudoのTopCoder日記

 | 

2016-04-26

EmployManager

| 15:58

#include <iostream>
#include <vector>
#include <string>

using namespace std;
using ll = long long;

class EmployManager {
 public:
  int maximumEarnings(vector<int> value, vector<string> earning) {
    ll se = 0;
    int ans = Eval(value, earning, se);
    bool changed = true;
    while (changed) {
      changed = false;
      ll curse = se;
      for (ll i = 0; i < value.size(); ++i) {
        if (se & (1LL << i)) continue;
        const int cur = Eval(value, earning, se | (1LL << i));
        if (cur > ans) {
          changed = true;
          curse = se | (1LL << i);
          ans = cur;
        }
      }
      se = curse;
    }
    return ans;
  }

  int Eval(const vector<int>& value, const vector<string>& earning, ll se) {
    int ans = 0;
    for (ll i = 0; i < value.size(); ++i) {
      if (se & (1LL << i)) {
        ans -= value[i];
      }
    }
    for (ll i = 0; i < value.size(); ++i) {
      for (ll j = i + 1; j < value.size(); ++j) {
        int cost = earning[i][j] - '0';
        if ((se & (1LL << i)) && (se & (1LL << j))) {
          ans += cost;
        } else if (!(se & (1LL << i)) && !(se & (1LL << j))) {
          ans -= cost;
        }
      }
    }
    return ans;
  }
};

貪欲提案おじさん

(証明できて)ないです

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/peryaudo/20160426
 |