#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
struct node
{
int s,f;
};
vector<node>pq;
int ans = -1,n,tots,totf;
int sum[120];
void dfs(int step)
{
if(step == n) {
if(tots >= 0 && totf >= 0) {
ans = max(ans, totf + tots);
} return;
}
if(totf + tots + sum[step] <= ans) return ; //当前加从当前到最后的最优情况都<=ans,则剪枝。
if(pq[step].f + pq[step].s < 0 && tots + totf <= ans) return; //因为是排序好的，后来的一定有f + s < 0，所以截止到现在最优就是tots + totf,小于ans,剪枝。
totf += pq[step].f , tots += pq[step].s;
dfs(step + 1); //要当前这个继续dfs
totf -= pq[step].f , tots -= pq[step].s;
dfs(step + 1); //不要当前这个继续dfs;
}
bool cmp(node a1,node a2)
{
return a1.s + a1.f > a2.s + a2.f;
}
int main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i ++) {
int s,f;
cin >> s >> f;
node w; w.f = f,w.s = s;
if(f == 0 && s == 0) continue;
if(f <= 0 && s <= 0) continue;
if(f >= 0 && s >= 0) {
totf += f , tots += s;
}
else pq.push_back(w);
}
ans = totf + tots;
n = pq.size();
sort(pq.begin(), pq.end(), cmp); //important
for(int i = n - 1;i >= 0;i --) {
if(pq[i].f + pq[i].s <= 0) sum[i] = 0; // pq[i].f + pq[i].s > pq[i - 1].f + pq[i - 1].s
else sum[i] = sum[i + 1] + pq[i].f + pq[i].s;
}
dfs(0);
cout << ans << endl;
return 0;
}
先水一发用DFS写的，精髓在于排序和剪枝，以及那个函数sum,如果不排序肯定会错，想想为什么。代码注释很清楚。
