SRM647div1med:CtuRobots
なんとなくアルゴリズム的に正しい気がするけど本当にあってるのかがよくわからない。どう証明するのかわかる人いたら教えていただけると助かります。
問題:http://community.topcoder.com/stat?c=problem_statement&pm=13595&rd=16279
解法:
以下ソースコード
const int MAXB = 10010; const int MAXN = 555; double dp[MAXN][MAXB]; class CtuRobots { public: double maxDist(int B, vector <int> cost, vector <int> cap) { int n = cost.size(); vector<pair<int, int> > P(n); for (int i = 0; i < n; i++) { P[i] = make_pair(cap[i], cost[i]); } sort(P.begin(), P.end()); for (int i = 0; i < MAXN; i++) for (int j = 0; j < MAXB; j++) dp[i][j] = -1; dp[0][B] = 0; for (int i = 1; i <= n; i++) { for (int b = 0; b <= B; b++) { dp[i][b] = dp[i-1][b]; if (b+P[i-1].second <= B && dp[i-1][b+P[i-1].second] > -1) { dp[i][b] = max(dp[i][b], P[i-1].first + dp[i-1][b+P[i-1].second]/3); } } } double ret = 0; for (int i = 0; i <= B; i++) ret = max(ret, dp[n][i]); return ret/2; } }; <||