TopCoder SRM 619 Div2 Hard EmployManager

Div1 Mediumについでこちらもグラフかと思ったら違った。
http://community.topcoder.com/stat?c=problem_statement&pm=13116

問題

N人の社員を採用するか検討している。
1人を採用するとvalue[i]だけコストがかかる。

i < jであるi番とj番の社員において：

• 2人とも採用すると、earning[i][j]の利益を得られる。
• 2人とも不採用だと、earning[i][j]だけ損する。
• 片方だけ採用すると、何も起きない。

最終的な利益、すなわち採用による利益の和から採用コストと不採用による損を引いたものを最大化せよ。

解法

採用について以下のように考えるとよい。

• 基本的にearning[i][j]だけ損する。
• iとj、それぞれ1人採用するたびに利益がearning[i][j]増える。

こうするとiとjを独立に計算できる。

あとはi番を採用するかどうかは かどうかで決めればよい。

class EmployManager {
	public:
	int N;
	int maximumEarnings(vector <int> value, vector <string> earning) {
		N=value.size();
		int ret=0,x,y;
		FOR(x,N) {
			int val=0;
			FOR(y,N) val+=earning[x][y]-'0';
			ret += max(0,val-value[x]);
		}
		FOR(x,N) for(y=x+1;y<N;y++) ret -= earning[x][y]-'0';
		return ret;
	}
}

まとめ

最初難しく考えすぎたけど、よくよく見たら簡単だった。