题意分析

题目要求从若干奶牛中挑选子集，使得选中奶牛的总聪明度（TS）和总趣味度（TF）都不小于 0，并且要让TS + TF 的值最大。如果不存在任何满足条件的子集，输出 0。

每头奶牛的聪明度和趣味度可能为负数，因此需要考虑如何组合正负值，使得总和非负且总和最大。 核心难点：在满足 $TS ≥ 0$ 和 $TF ≥ 0$ 的前提下，找到 $TS+TF$ 的最大值。

解题思路

核心思想：动态规划（DP）

通过动态规划记录 “选择奶牛后总聪明度对应的最大总趣味度”，然后筛选出符合条件的状态，计算最大值。

具体步骤

1.状态定义

用一个数组dp记录状态，其中dp[s]表示总聪明度为s时，能达到的最大总趣味度。 由于聪明度可能为负数$（最小 - 1000×100=-100000）$，需要给s加上一个偏移量（如 1e5），避免数组索引为负数。例如，实际存储时用s + 1e5作为索引。

2.初始化

初始时未选任何奶牛，总聪明度为 0，总趣味度为 0。因此dp[0 + 偏移量] = 0，其余状态初始化为最小值（表示不可达）。

3.状态转移

遍历每头奶牛，对于当前奶牛的聪明度si和趣味度fi，更新dp数组：

不选当前奶牛：状态不变，直接继承之前的dp值。 选当前奶牛：如果之前总聪明度为s_prev时可达，那么新的总聪明度为$s_{prev} + s_i$，总趣味度为$dp[s_prev] + f_i$。 对每个可能的s_prev，计算新状态s_new = s_prev + si，并更新dp[s_new]为两者中的较大值（选或不选的最优解）。

结果筛选

遍历所有可能的总聪明度s（需≥0），检查对应的总趣味度dp[s]是否≥0。若满足条件，则计算s + dp[s]，取最大值。

若所有状态都不满足条件（即不存在 TS≥0 且 TF≥0 的子集），输出 0。

代码

#include<iostream>
using namespace std;
const int maxs=-100001;
const int base=100000;
struct{
     int v;
     int d;
     bool flag;       
}f[2*base];
int num[100][2];
int up=base,down=base,n;
void dp(){
     for(int i=down;i<=up;i++) f[i].v=maxs;
     f[base].v=0;
     for(int i=0;i<n;i++){
          for(int j=down;j<=up;j++)
              if(f[j].v!=maxs && f[j].v+num[i][1]>f[j+num[i][0]].v){
                    f[j+num[i][0]].flag=true; 
                    f[j+num[i][0]].d=f[j].v+num[i][1];                
              }
          for(int j=down;j<=up;j++)
              if(f[j].flag){ 
                   f[j].v=f[j].d; 
                   f[j].flag=false;
              }
     }     
     int sum=base;
     for(int i=base;i<=up;i++) 
          if(f[i].v!=maxs && f[i].v>=0 && i+f[i].v>sum) 
               sum=i+f[i].v;
     cout<<sum-base<<endl;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
         scanf("%d%d",&num[i][0],&num[i][1]);
         if(num[i][0]>0) up+=num[i][0];
         else down+=num[i][0];        
    }
    dp();
    system("pause");
    return 0;
}
```

```