写出了$O((n+m)k^2)$的算法，但是却看不懂$O(nmk)$的算法。
首先说$O((n+m)k^2)$的算法。
把所有牛放在一起从大到小排序，相同则$A$的牛放在前面，问题变为从序列中选择一些元素，使得任意前缀$A$入选的个数大于$B$入选的个数。
$f[i][j][k]$表示考虑了前$i$头牛，$A$入选了$j$头，$B$比$A$少$k$头，转移就判断下一头牛是$A$的还是$B$的，如果是$B$还要判断当前状态$k$是不是等于$0$。
具体看代码吧。
#include <bits/stdc++.h> #define Mid ((l + r) >> 1) #define lson (rt << 1) #define rson (rt << 1 | 1) using namespace std; const int mod = 1e9 + 9; int read(){ char c; int num, f = 1; while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; while(c = getchar(), isdigit(c)) num = num * 10 + c - '0'; return f * num; } struct node { int x, t; } a[2009]; int n, m, p, f[2009][2009][20]; int cmp(node a, node b) { return (a.x == b.x && a.t > b.t) || a.x > b.x; } void up(int &a, int b) {a = (a + b) % mod;} signed main() { n = read(); m = read(); p = read(); for(int i = 1; i <= n; i++) a[i] = (node){read(), 1}; for(int i = 1; i <= m; i++) a[i + n] = (node){read(), 2}; sort(a + 1, a + 1 + n + m, cmp); f[0][0][0] = 1; for(int i = 0; i <= n + m; i++) { for(int j = 0; j <= min(i, p); j++) { for(int k = 0; k <= j; k++) { up(f[i + 1][j][k], f[i][j][k]); if(a[i + 1].t == 1) up(f[i + 1][j + 1][k + 1], f[i][j][k]); if(a[i + 1].t == 2 && k) up(f[i + 1][j][k - 1], f[i][j][k]); } } } printf("%lld ", f[n + m][p][0]); return 0; }
然后看到luogu题解里面一个$O(nmk)$的算法。
他的递推是这样的
for (int i=1;i<=p;i++){ for (int j=1;j<=n;j++) for (int k=1;k<=m;k++) if (a[j]>b[k]) f[i][j][k]=f[i-1][j-1][k-1]; for (int j=1;j<=n;j++) for (int k=1;k<=m;k++) f[i][j][k]=(f[i][j][k]+f[i][j][k-1])%mo; for (int j=1;j<=n;j++) for (int k=1;k<=m;k++) f[i][j][k]=(f[i][j][k]+f[i][j-1][k])%mo; }
$f[i][j][k]$表示匹配了$i$对，A仅使用前$j$只，B仅使用前$k$只的方案数。
一开始我想的这个复杂度算法递推是$f[i][j][k]=f[i-1][j][k]+f[i][j - 1][k]$以为是和$LCS$一样的处理方法，然而不行，因为会有方案重复，但是它的代码却对了，于是考虑为什么。
发现他第一句计算出来后$f[i][j][k]$代表的意义是：匹配了$i$对，A第$j$只必选，B第$k$只必选的方案数。
然后第二句，它固定了$j$相当于对$j$求了一个前缀和，代表的意义是：匹配了$i$对，A第$j$只必选，B考虑前$k$只的方案数。
然后第三句，它固定了$k$相当于对$j$求了一个前缀和，代表的意义是：匹配了$i$对，A考虑前$j$只，B考虑前$k$只的方案数。
心里只有一句妙啊。