500 FoxAndDoraemon

2012-04-08

22:55 |

i番目以降のtaskを処理する最短時間というDPでやろうとしてうまくいかないことに気づく
範囲にしないといかん
連鎖行列積の問題みたく [begin, end) を使った最短時間をメモ化。
が！一箇所 max が min になってて WA
最初全部 max にしててあれ最短だから min だ、あでもサブツリーの時間は長い方だ...とかいってるうちに直し漏れが生じた模様
(´Д｀)
(2個と3個の場合の処理いらないし)

↓修正版(test pass in practice room)

vector <int> WC;
int SC;
int N;
map<PII, int> memo;
class FoxAndDoraemon {
	public:
	// [i0, i1)
	int f(int i0, int i1) {
		PII key=MP(i0, i1);
		if(memo.count(key)) return memo[key];
		int rest = i1-i0;
		if(rest<=0) return memo[key] = 0;
		if(rest==1) return memo[key] = WC[i0];
		if(rest==2) return memo[key] = SC+max(WC[i0], WC[i0+1]);
		if(rest==3) return memo[key] = SC+max(WC[i0], SC+max/*min*/(WC[i0+1], WC[i0+2]));
		// >=4
		int ans = 1000000;
		for(int i=1;i<rest;i++) {
			int c = SC+max(f(i0, i0+i), f(i0+i, i1));
			ans = min(ans, c);
		}
		return memo[key] = ans;
	}
	int minTime(vector <int> _WC, int _SC) {
		sort(ALLR(_WC));
		WC=_WC;
		SC=_SC;
		memo.clear();
		N=WC.size();
		int ans = f(0, N);
		return ans;
	}
};