一道DP，用f[i][j][k1][k2]表示取到只剩下i个男的，j个女的时，最大的男的个数与最大的女的个数分别为k1,k2
最终的方案总数
状态转移方程自己列，下面是代码
#include<iostream> #include<fstream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int n,m,k; int jiyi[153][153][23][23]; const int mod=12345678; int dp(int nan,int nv,int k1,int k2){ int& fanhui=jiyi[nan][nv][k1][k2]; if(fanhui!=-1){ return fanhui; }else{ if(k1>k||k2>k){ return fanhui=0; }else{ if(nan==0&&nv==0){ return fanhui=1; }else{ fanhui=0; if(nan>0){ fanhui+=dp(nan-1,nv,k1+1,max(0,k2-1)); fanhui%=mod; } if(nv>0){ fanhui+=dp(nan,nv-1,max(0,k1-1),k2+1); fanhui%=mod; } } } } return fanhui; } int main(){ cin>>n>>m>>k; for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ for(int k1=0;k1<=k+1;k1++){ for(int k2=0;k2<=k+1;k2++){ jiyi[i][j][k1][k2]=-1; } } } } int ans=dp(n,m,0,0); cout<<ans<<endl; return 0; } /* in: 1 2 1 out: 1 */