[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=4742

[算法]

动态规划

用Fi,j,k表示约翰的前i头牛和保罗的前j头牛匹配 , 共选了k头 , 有多少种方案

转移详见代码

时间复杂度 : O(N ^ 2K)

[代码]

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1010
#define MAXT 12
const int P = 1e9 + ; int n , m , t;
int a[MAXN] , b[MAXN];
int dp[MAXN][MAXN][MAXT]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
} int main()
{ read(n); read(m); read(t);
for (int i = ; i <= n; i++) read(a[i]);
for (int i = ; i <= m; i++) read(b[i]);
sort(a + , a + n + );
sort(b + , b + m + );
dp[][][] = ;
for (int i = ; i <= n; i++)
{
for (int j = ; j <= m; j++)
{
for (int k = ; k <= t; k++)
{
if (i + j == ) continue;
if (i == ) dp[i][j][k] = dp[i][j - ][k];
else if (j == ) dp[i][j][k] = dp[i - ][j][k];
else dp[i][j][k] = dp[i - ][j][k] + dp[i][j - ][k] - dp[i - ][j - ][k];
dp[i][j][k] = (dp[i][j][k] % P + P) % P;
if (k > && a[i] > b[j]) dp[i][j][k] += dp[i - ][j - ][k - ];
dp[i][j][k] = (dp[i][j][k] % P + P) % P;
}
}
}
printf("%d\n" , dp[n][m][t]); return ; }
05-20 00:39
查看更多