Steven_MengのBlog

传送门

比较有意思的$DP$ 题目,考虑转化题目条件:

原题目:对于任意连续的一段,男女数目之差不超过$k$

转化成:对于所有的连续的段,男女数目之差的最大值不超过$k$

然后就可以$DP$了,令$dp[i][j][x][y]$为前$i+j$人中$i$人为男孩,$j$人为女孩,对于前$i+j$人中所有连续的段,男减女最多$x$ 人,女减男最多$y$人的方案数。

考虑新加进的是男孩,即$dp[i+1][j][x+1][max(y-1,0)]+=dp[i][j][x][y]$

新加进的是女孩,即$dp[i][j][max(x-1,0)][y]+=dp[i][j][x][y]$

时间复杂度$O(nmk^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define MAXN 155
#define MAXM 25
#define MOD 12345678
using namespace std;
int dp[MAXN][MAXN][MAXM][MAXM];
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int main(){
int n=read(),m=read(),k=read();
dp[0][0][0][0]=1;
for (register int i=0;i<=n;++i){
for (register int j=0;j<=m;++j){
for (register int x=0;x<=k;++x){
for (register int y=0;y<=k;++y){
dp[i+1][j][x+1][max(y-1,0)]+=dp[i][j][x][y];
dp[i+1][j][x+1][max(y-1,0)]%=MOD;
dp[i][j+1][max(0,x-1)][y+1]+=dp[i][j][x][y];
dp[i][j+1][max(0,x-1)][y+1]%=MOD;
}
}
}
}
int ans=0;
for (register int i=0;i<=k;++i){
for (register int j=0;j<=k;++j){
ans=(ans+dp[n][m][i][j])%MOD;
}
}
printf("%d\n",ans);
}

 评论