(周赛t3) 2212. 射箭比赛中的最大得分

2212. 射箭比赛中的最大得分

自己写的dfs，太麻烦了，不如状压dp
还有个坑就是箭必须用完

class Solution {
public:
    vector<int> maximumBobPoints(int numArrows, vector<int>& arr) {
        int n = arr.size();
        vector<int> res;
        int score=0, sum = 0;
        for(auto c:arr) sum += c;
        
        for(int mask = 0; mask < 1<<n; mask++){
            int cur = 0, csum = 0;
            vector<int> b(n,0);
            for(int i = 0; i < n; i++){
                if((mask >> i) & 1) b[i] = arr[i] + 1;
                if(b[i] > arr[i]) cur += i;
                csum += b[i];
            }
            if(csum <= sum && cur > score){
                b[0] += sum - csum;
                score = cur;
                res = b;
            }
        }
        return res;
    }
};