排队问题中，如何优化等待时间？

本文共计646个文字，预计阅读时间需要3分钟。

题目：一道学校内部测试赛的题目，关于DP方法的应用。

内容：给定一个包含i个男生和j个女生的班级，最后一个人站的位置是男生（1）或女生（0）的方法数。在男生数量没有超过k1的情况下，dp[i][j][0]表示前i个男生和j个女生时，最后一个人是女生的方法数。

一道学校内部测试赛的题目，对于这题我们采用的方法是DP。

dp[i][j][0~1]表示有i个男生j个女生时，最后一个人站的是男生(1)或女生(0)的方法数。

在男生个数没有超过k1的时候：dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1]。

在女生个数没有超过k2的时候：dp[i][j][1] = dp[i][j-1][0] + dp[i][j-1][1]。

在男生个数超过k1的时候：dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1] - dp[i-k1-1][j][0]。(相当于减去从第j+i-k1位开始之后都是男生的连续k1和男生的情况)

在女生个数超过k2的时候：dp[i][j][1] = dp[i][j-1][1] + dp[i][j-1][0] - dp[i][j-k2-1][1]。(同上)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100+5;
const int MOD = 1e8;
int dp[maxn][maxn][2];
int x,y,k1,k2;
int main()
{
while(scanf("%d%d%d%d", &x,&y,&k1,&k2) !=EOF)
{
memset(dp,0,sizeof(dp));
int i,j;
for(i=1; i<=k1; i++) dp[i][0][1] = 1;
for(j=1; j<=k2; j++) dp[0][j][0] = 1;
for(i=1; i<=k1 && i<=x; i++)
{
for(j=1; j<=k2 && j<=y; j++)
{
dp[i][j][0] = (dp[i][j-1][1] + dp[i][j-1][0])%MOD;
dp[i][j][1] = (dp[i-1][j][1] + dp[i-1][j][0])%MOD;
}
for( ; j<=y; j++)
{
dp[i][j][0] = (dp[i][j-1][1] + dp[i][j-1][0] - dp[i][j-k2-1][1]+MOD)%MOD;
dp[i][j][1] = (dp[i-1][j][1] + dp[i-1][j][0])%MOD;
}
}
for( ; i<=x; i++)
{
for(j=1; j<=k2 && j<=y; j++)
{
dp[i][j][0] = (dp[i][j-1][1] + dp[i][j-1][0])%MOD;
dp[i][j][1] = (dp[i-1][j][1] + dp[i-1][j][0] - dp[i-k1-1][j][0]+MOD)%MOD;
}
for( ; j<=y; j++)
{
dp[i][j][0] = (dp[i][j-1][1] + dp[i][j-1][0] - dp[i][j-k2-1][1]+MOD)%MOD;
dp[i][j][1] = (dp[i-1][j][1] + dp[i-1][j][0] - dp[i-k1-1][j][0]+MOD)%MOD;
}
}
printf("%d\n", (dp[x][y][1]+dp[x][y][0])%MOD);
}
}