1
class Solution:
2
    def generateValidStrings(self, n: int, k: int) -> list[str]:
3
        ans = []
4
        def dfs(i,ok,cost,path):
5
            if i == n:
6
                ans.append(''.join(path))
7
                return
8
            path.append('0')
9
            dfs(i+1,False,cost,path)
10
            path.pop()
11

12
            if not ok and cost + i <= k:
13
                path.append('1')
14
                dfs(i+1,True,cost+i,path)
15
                path.pop()
16
        dfs(0,False,0,[])
17
        return ans

1
class Solution {
2
public:
3
    vector<string> generateValidStrings(int n, int k) {
4
        vector<string> ans;
5
        string path;
6
        function<void(int,bool,int)> dfs = [&](int i,bool ok,int cost){
7
            if(i == n){
8
                ans.push_back(path);
9
                return;
10
            }
11
            path.push_back('0');
12
            dfs(i+1,false,cost);
13
            path.pop_back();
14

15
            if(!ok && cost + i <= k){
16
                path.push_back('1');
17
                dfs(i+1,true,cost+i);
18
                path.pop_back();
19
            }
20
        };
21
        dfs(0,false,0);
22
        return ans;
23
    }
24
};

1
cost = [0] * (1 << 12)
2
for x in range(1, len(cost)):
3
    if x & (x >> 1):  # 有两个连续的 1
4
        cost[x] = inf  # 不合法
5
    else:
6
        # 去掉 x 中的一个比特位（最低位还是最高位都可以），计算 DP
7
        i = x.bit_length() - 1
8
        cost[x] = cost[x ^ (1 << i)] + i
9

10
class Solution:
11
    def generateValidStrings(self, n: int, k: int) -> List[str]:
12
        ans = []
13
        s = [''] * n
14
        for x in range(1 << n):
15
            if cost[x] > k:
16
                continue
17
            for j in range(n):  # 注意左边是低位，右边是高位
18
                s[j] = str(x & 1)
19
                x >>= 1
20
            ans.append(''.join(s))
21
        return ans

1
class Solution:
2
    def maximumSum(self, nums: List[int], m: int, left: int, right: int) -> int:
3
        n = len(nums)
4
        s = list(accumulate(nums, initial=0))  # nums 的前缀和
5

6
        # f[i][j] 表示在前 j 个数（下标 0 到 j-1）中选出恰好 i 个子数组，所选元素之和的最大值
7
        f = [[-inf] * (n + 1) for _ in range(m + 1)]
8
        f[0] = [0] * (n + 1)
9

10
        for i in range(1, m + 1):
11
            q = deque()
12

13
            # 前 i 个子数组至少占用了 i * left 个位置
14
            for j in range(i * left, n + 1):
15
                # 1. 入
16
                k = j - left
17
                v = f[i - 1][k] - s[k]
18
                while q and f[i - 1][q[-1]] - s[q[-1]] <= v:
19
                    q.pop()
20
                q.append(k)
21

22
                # 2. 更新
23
                # 不选 nums[j-1] vs 选一个以 j-1 结尾的子数组
24
                f[i][j] = max(f[i][j - 1], f[i - 1][q[0]] - s[q[0]] + s[j])
25

26
                # 3. 出，下一轮循环队首离开窗口
27
                if q[0] <= j - right:
28
                    q.popleft()
29

30
        # 枚举恰好选 i 个子数组
31
        return max(f[i][n] for i in range(1, m + 1))