mayoko’s diary

プロコンとかいろいろ。

SRM647div1med:CtuRobots

なんとなくアルゴリズム的に正しい気がするけど本当にあってるのかがよくわからない。どう証明するのかわかる人いたら教えていただけると助かります。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13595&rd=16279

解法:
f:id:mayokoex:20150325111857j:plain
以下ソースコード

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;
    }
};
<||