传送门：点击打开链接
题意：n(一定为偶数)块蛋糕，每块蛋糕Alice有一个权值，Bob有一个权值。每一次Alice选择两块蛋糕给Bob看，Bob会选择出他的观点的权值最大的蛋糕，然后Alice拿剩下的那一块，问Alice能获得的最大总权值是多少
思路：我们可以发现，Bob的权值最大的那一块，无论如何，一定最后会给Bob。那么我们能发现其中好像存在一点规律。
如果我们按照Bob认为的权值从大到小排序，然后再考虑如何取蛋糕。设dp[i][j]为正在考虑第i块蛋糕，Alice已经取了j块，我们能发现，只有j<=i/2才满足题意，只有这样才能转移方程。因为Bob选的数量一定要随时大于等于Alice选的数量，这里跟卡特兰数的思路是很像的(其实说白了如果问的是情况数，就是卡特兰数..),想到这里转移方程就可以列出来了。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck printf("fuck")
#define FIN freopen("input.in","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int MX = 1e3 + 5;struct Data {int a, b;Data() {}Data(int _a, int _b) {a = _a; b = _b;}bool operator<(const Data &B)const {return b > B.b;}
} D[MX];int dp[MX][MX];int main() {int T, n; //FIN;scanf("%d", &T);while(T--) {memset(dp, 0, sizeof(dp));scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%d%d", &D[i].a, &D[i].b);}sort(D + 1, D + 1 + n);for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {dp[i][j] = dp[i - 1][j];if(i / 2 >= j) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + D[i].a);}}printf("%d\n", dp[n][n / 2]);}return 0;
}