[LintCode] Coins in a line II

3037 단어 dplintcode
Note: Both player are intelligent. dp[i] indicates the maximum value we can get from position i to the end of coins. There are two choices: 1st: We take only one coins which has values[i], then the other player will give us a choices between min(dp[i+2], dp[i+3]), ( she takes one or two coins). 2nd: Same as above analyze, we take two coins, then the max value we will get is values[i] + values[i+1] + min(dp[i+3],dp[i+4]). Finally, if dp[0] > sum - dp[0] we can win or we lose.(sum is the total value of the coins, dp[0] means the maximum possible value we can get from first coin to the last one). 
    class Solution {
public:
    /** * @param values: a vector of integers * @return: a boolean which equals to true if the first player will win */
    bool firstWillWin(vector<int> &values) {
        // write your code here
        int n = values.size();
        if(n<=2) return true;
        vector<int> dp(n+1,0);
        dp[n-1] = values[n-1];
        dp[n-2] = values[n-2] + values[n-1];
        for(int i = n-3; i>=0; --i){
            int val1 = values[i] + min(((i+2)<=n ? dp[i+2] : 0), ((i+3<=n) ? dp[i+3] :0));
            int val2 = values[i] + values[i+1] + min(((i+3)<=n ? dp[i+3] : 0), ((i+4<=n) ? dp[i+4] :0));
            dp[i] = max(val1, val2);
        }
        int sum = accumulate(values.begin(), values.end(), 0);
        return dp[0] > sum - dp[0];
    }
};
웨이트, 새로운 웹 킬러?!😮
POJ-1458 Common Subsequence(선형 게이지, 최대 공통 하위 시퀀스 문제)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage