PO65最后的士兵

思路：动态规划

#include <vector>
#include <numeric>
using namespace std;

class Solution
{
public:
    int lastStoneWeightII(vector<int> &nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int n = nums.size(), m = sum / 2;
        vector<vector<int> > dp(n + 1, vector<int>(m + 1));
        dp[0][0] = true;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j <= m; ++j)
            {
                if (j < nums[i])
                {
                    dp[i + 1][j] = dp[i][j];
                }
                else
                {
                    dp[i + 1][j] = dp[i][j] || dp[i][j - nums[i]];
                }
            }
        }
        for (int j = m;; --j)
        {
            if (dp[n][j])
            {
                return sum - 2 * j;
            }
        }
    }
};

int main()
{
    Solution solution;
    vector<int>nums;
    int n, temp;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        nums.push_back(temp);
    }
    cout << solution.lastStoneWeightII(nums) << endl;
    return 0;
}

-[1]最后一块石头的重量 II

PO65最后的士兵

原文：https://www.cnblogs.com/aoke2002/p/15270535.html