题意：给你$N$个数，你可以将其划分为若干对集合（这里所说的集合允许数字重复）（即集合是两个集合两个集合出现），每对集合中两个集合所有元素的和的差的绝对值不超过$M$，可以有数字不在集合内，可以有集合为空。求所有集合内数的和的最大值。$N \leq 100 , M \leq 100$，数字$\leq 100$
虽然考试的时候没做出来但还是感觉这是一道大水题
可以发现：划分若干对集合和划分一对集合是等效的，因为假如说一对集合$A,B$中$\sum A \leq \sum B(\sum A$表示集合$A$中所有元素的和$)$，另一对集合$C,D$满足$\sum C \leq \sum D$，那么集合$A+D,B+C$一定是满足条件的（显然）。所以我们就是要划分两个集合使得其差的绝对值不超过$M$且和最大。经典的01背包拔河问题
#include<bits/stdc++.h>
using namespace std;
] , pot[];
int main(){
ios::sync_with_stdio();
cin.tie();
cout.tie();
int N , M;
cin >> N >> M;
memset(pot , -0x3f , sizeof(pot));
memset(dp , -0x3f , sizeof(dp));
dp[] = ;
; i <= N ; i++){
int a;
cin >> a;
; j++)
pot[j - a] = max(pot[j - a] , dp[j] + a);
; j <= - a ; j++)
pot[j + a] = max(pot[j + a] , dp[j] + a);
; j <= ; j++)
dp[j] = max(dp[j] , pot[j]);
}
;
; i <= + M ; i++)
ans = max(ans , dp[i]);
cout << ans;
;
}