UVa 10128 Queue （DP）

UVa 10128 Queue （DP）2014-07-27 csdn博客 synapse7

10128 - Queue

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1069

既然有最优子结构，不妨从DP的角度来思考。

有三个不同的维度：总人数N，从前看到的人P，从后看到的人R。

假设现在队列由i-1个人变成了i个，由于谁后进到队列是无所谓的，不妨假设最矮的人是最后一个进入队列的，那么其所占的位置会有三种情况，第一种情况是站在队首，增加1个在前面能看到的人数，第二种情况是站在队尾，增加1个在后面能看到的人数，第三种情况是站在队伍中间，一共有i-2个位置可以站，但不会增加可见的人数。这样就能得到：

dp[i][j][k]=dp[i-1][j-1][k]+dp[i][j][k-1]+（i-2）*dp[i-1][j][k]

完整代码：

/*0.019s*/#include<cstdio>#include<cstring>long long f[20][20][20];void prepare（）///组合太麻烦，果断递推之{int i, j, k;f[1][1][1] = 1;for （i = 2; i <= 13; ++i）for （j = 1; j <= i; ++j）for （k = 1; k <= i; ++k）f[i][j][k] = f[i - 1][j - 1][k] + f[i - 1][j][k - 1] + （i - 2） * f[i - 1][j][k];}int main（）{prepare（）;int t, N, P, Q;scanf（"%d", &t）;while （t--）{scanf（"%d%d%d", &N, &P, &Q）;printf（"%lld
", f[N][P][Q]）;}return 0;}