20pts

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> s(n), a(n);
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < n; i++) cin >> a[i];
    
    // 对每个 X
    for (int X = 1; X <= n; X++) {
        int ans = 0;
        
        // 枚举所有子集 (0 到 2^n - 1)
        for (int mask = 0; mask < (1 << n); mask++) {
            int cnt = 0;
            int sum_a = 0;
            int max_s = 0;
            
            // 统计这个子集
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    cnt++;
                    sum_a += a[i];
                    max_s = max(max_s, s[i]);
                }
            }
            
            // 如果大小正好是 X
            if (cnt == X) {
                int fatigue = sum_a + 2 * max_s;
                ans = max(ans, fatigue);
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

40pts

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;  // N ≤ 100，稍微开大一点

int s[MAXN], a[MAXN];
int temp[MAXN];  // 临时数组用于排序

int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < n; i++) cin >> a[i];
    
    // 对每个 X
    for (int X = 1; X <= n; X++) {
        int ans = 0;
        
        // 枚举最远住户 i（从 X-1 开始，因为前面至少要有 X-1 个住户可选）
        for (int i = X - 1; i < n; i++) {
            // 将前 i 个 a 值（索引 0 到 i-1）复制到 temp 数组
            for (int j = 0; j < i; j++) {
                temp[j] = a[j];
            }
            
            // 对前 i 个元素进行降序排序（只排序前 i 个）
            sort(temp, temp + i, greater<int>());
            
            // 计算最大的 X-1 个之和
            int sum_a = a[i];  // 先加上第 i 家的推销疲劳（必须选）
            for (int j = 0; j < X - 1; j++) {
                sum_a += temp[j];
            }
            
            // 总疲劳 = 推销疲劳 + 步行疲劳（往返距离 = 2 * s[i]）
            int fatigue = sum_a + 2 * s[i];
            
            if (fatigue > ans) ans = fatigue;
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

贪心(100pts)

• 假设前$x$的个最大的家庭在$l$的位置,那么我们如果想要疲劳值更大，那么我们只需要枚举$l$右边的点【实际上枚举左边的点也没有问题，只是不会更新答案】，可以尝试将最小的$a_i$换成$a_i+2*s_i$,最后的最大值就是最后的答案。为了枚举方便，实际上我们是枚举所有小于等于$a_i$的$a_i+2*s_i$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Node{
    int s;
    int a;
};
Node node[N];
bool cmp(Node x,Node y)
{
    if(x.a>y.a) return true;
    if(x.a==y.a&&x.s>y.s) return true;
    return false;
}
//f[i]表示前i个 Ai 的和；
//g[i]表示前i个 Si 的最大值；
//s[i]表示i~n中  2Si+Ai  的最大值；
int f[N],g[N],s[N],res[N];
int main()
{
    int n;
  	cin>>n;
    for(int i=1;i<=n;i++) cin>>node[i].s;
    for(int i=1;i<=n;i++) cin>>node[i].a;
    sort(node+1,node+1+n,cmp); //按照疲劳值进行排序 
    for(int i=1;i<=n;i++)
    {
        f[i]=f[i-1]+node[i].a; //前i家的疲劳值 
        g[i]=max(g[i-1],node[i].s); //前i家最远的距离 
    }
    for(int i=n;i;i--)
    {
        s[i]=max(s[i+1],2*node[i].s+node[i].a); //i..n两倍距离+疲劳值最大的点 
    }
    for(int i=1;i<=n;i++)
    {
    	cout<<max(f[i]+g[i]*2,f[i-1]+s[i])<<endl;
        //  (前i个最大的)疲劳最大+2倍距离   前i-1个疲劳+最后一个单独走 
    }
    return 0;
}