SRM 605 div1 easy AlienAndHamburgers

ひえ〜〜めっちゃ失敗した

概要

とある宇宙人は地球を滅ぼす前にハンバーガーを食べたいと思った。
N 個のハンバーガーがある。各ハンバーガーは二つの属性 type と taste をもち、それぞれ整数値で表される。
これらのハンバーガーのうち、いくつかを選んで食べる。（食べた種類の数 × taste の合計）が最大となるように食べたときの、この値を求めよ。

失敗談

DPをしようとおもった

DP案1

dp[何個目についてみるか][何種類とったか] = 合計のtaste

今思うと自分頭悪すぎ..

これだと最終的に何種類とったかわからない、そうすると2種類とって100っていうのと、3種類とって99だと2*100<3*99なのに100>99なので2種類しか取っていない100が採用される。
「何種類とったか」が関係するのではなくて、「最終的に何種類とったか」が関係する、、ので、、

DP案2

「何種類とったか」が関係するのではなくて、「最終的に何種類とったか」が関係する、、ので、、

• >　せやな、dp[何個目についてみるか][何種類とったか] = 合計のtaste * 合計のtypesにしたろ

今思うと自分頭わるすぎ,,,(n回目）
なぜかというと[何個目についてみているか]以降のtasteの最大値じゃあ、何種類とったほうがいいかというのは判断できない

例)
i個目までに
1000のtaste
i個目以降では
2種類とって-100
3種類とって-200

の時に-100*2>-200*3だが、i個目までの合計を考えると
990*2<980*3

になる、、

教訓: i個目以前の結果が関連づいてくるDPは書いてはいけない（書くとしたら必ずdpの添字に追加する必要がある）

最終的に

i種類とるとき、tasteが最大値を取るときに最大になる！ｗと気づき、4時間かけてようやくソートして貪欲した、、頭悪い、、

見るとSugarDragon5君などが余裕でACしていて人生つらい気持ちになった
sugardragon5.hatenadiary.com

#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 998244353
#define INF 93193111451418101
#define bitcnt(a) (ll) __builtin_popcount((a))
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

bool positive[101];

ll maxTaste[103], tasteSum[103];
P dp[51][51];

set<ll> vis;

vector<ll> num;

class AlienAndHamburgers {

public:
  int getNumber(vector<int> type, vector<int> taste) {
    REP(i, 101) {
      maxTaste[i] = -INF;
    }
    REP(i, (signed)type.size()) {
      vis.insert(type[i]);

      if (taste[i] > 0) {
        positive[type[i]] = true;
        tasteSum[type[i]] += taste[i];
      }
      maxTaste[type[i]] = max(maxTaste[type[i]], (ll)taste[i]);
    }

    for (auto &a : vis) {
      if (positive[a]) {
        num.pb(tasteSum[a]);
      } else {
        num.pb(maxTaste[a]);
      }
    }
    sort(num.begin(), num.end(), greater<ll>());
    ll ret = 0, im = 0;
    REP(i, (signed)num.size()) {
      im += num[i];
      ret = max(ret, im * (i + 1));
    }
    return ret;
  }
};