526互联

取数游戏 Atcoder-abc128_d

发布时间 2023-08-07 17:32:17作者: Jeanny

枚举两端取了几个数，将手中的负数从小到大放回序列即可

#include <bits/stdc++.h>
using namespace std;
int n, m, a[55], c[55], ans = -0x7fffffff;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int l = 0; l <= n; l++) {
        for (int r = l + 1; r <= n + 1; r++) {  // r <= n+1
            int k = m - (l + (n - r + 1));
            //			cout<<"k: "<<k<<endl;
            if (k < 0)
                continue;
            int t = 0;
            memset(c, 0, sizeof c);
            for (int i = 1; i <= l; i++) c[++t] = a[i];
            for (int j = r; j <= n; j++) c[++t] = a[j];
            //			cout<<"t: "<<t<<endl;
            //			for(int i = 1; i <= t; i++)
            //				cout<<"c[]"<<i<<" "<<c[i]<<endl;
            sort(c + 1, c + t + 1);
            int p = 1, sum = 0;
            //			for(int i = 1; i <= t; i++)
            //				cout<<"c[]"<<i<<" "<<c[i]<<endl;
            while (c[p] < 0 && k > 0) p++, k--;
            //			cout<<"p:"<<p<<endl;
            for (int j = p; j <= t; j++) sum += c[j];
            ans = max(ans, sum);
        }
    }
    cout << ans << endl;
    return 0;
}

记忆化搜索
dfs(l+1,r,k-2) 扔回去的操作可以是先不扔，最后扔。如果扔回去还要再拿回来，没有意义，相当于不扔。因此序列的长度是[l+1,r]