TopCoder SRM 605 Div1 Easy AlienAndHamburgers

また問題文をちゃんと読まずにケアレスミスでEasyを落とした。
Mediumも問題文を把握せず落としたし散々。
http://community.topcoder.com/stat?c=problem_statement&pm=12948

問題

N個のハンバーガーがあり、それぞれの種類type[i]と味taste[i]が与えられる。
N個のうち幾つかを食べたとき、満足度は種類の数と味の総和の積となる。
最大の満足度を答えよ。

解法

taste[i]が0以上のハンバーガーは無条件に食べることを選択すればよい。
taste[i]が負のハンバーガーは、味の総和を減らすが種類を増やす効果があるため、満足度を増すか減らすか不明である。

よって、まずtaste[i]が0以上のものを集計しておく。
各種類について、taste[i]が負のハンバーガーしかないものはtaste[i]の最大値を覚えておく。
あとはこれら負のハンバーガーしかない種類を食べるか食べないかをDPで種類の数ごとに味の総和を最大化するDPを行えばよい。

なお、最後の手順はDPよりも簡単な方法もある。
同じ種類の数を選択するなら味の総和が高い方が良いので、taste[i]が負の種類についてそれらをソートして少ない順に幾つか選択していき、種類×味の総和を求めればよい。

int have[101];
int P[101];
int M[101];
ll dpdp[103][103];

class AlienAndHamburgers {
	public:
	int getNumber(vector <int> type, vector <int> taste) {
		int i,j,k;
		int N=type.size();
		ZERO(have);
		ZERO(P);
		ZERO(M);
		FOR(i,101) FOR(j,101) dpdp[i][j]=-1LL<<50;
		dpdp[0][0]=0;
		FOR(i,N) {
			type[i]--;
			if(taste[i]>=0) {
				have[type[i]]++;
				P[type[i]]+=taste[i];
			}
			else {
				if(M[type[i]]==0) M[type[i]]=taste[i];
				else M[type[i]]=max(M[type[i]],taste[i]);
			}
		}
		
		FOR(i,101) {
			if(have[i]==0 && M[i]==0) {
				FOR(j,101) dpdp[i+1][j]=dpdp[i][j];
			}
			else if(have[i]>0) {
				FOR(j,101) dpdp[i+1][j+1]=dpdp[i][j]+P[i];
			}
			else {
				FOR(j,101) {
					dpdp[i+1][j+1]=max(dpdp[i+1][j+1],dpdp[i][j]+M[i]);
					dpdp[i+1][j]=max(dpdp[i+1][j],dpdp[i][j]);
				}
			}
		}
		ll ret=-1LL<<50;
		FOR(i,101) ret=max(ret,dpdp[101][i]*i);
		return (int)ret;
	}
};

まとめ

本番、種類を1～100でなく1～50と見誤ったことなので非常にもったいない。
あとは無駄にDPをして時間をロスしたのがもったいなかったね。