正文

UVA 1638 Pole Arrangement

IP云
IP云V管理员/3 阅读
09/30
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

https://vjudge.net/problem/UVA-1638

题意：

n根长度分别为1,2,3,4……n的木棍

将这些木棍竖着排成一列

问从左边看能看到L根，从右边看能看到R根的方案数

将木棍从长到短放

dp[k][i][j] 表示再放第k根，从左边能看到i根，从右边能看到j根的方案数

放到最左边，从左边可以看到的木棍数+1

放到最右边，从右边可以看到的木棍数+1

放到中间，看到的木棍数不变

所以动态转移方程：dp[k][i][j]=dp[k-1][i-1][j]+dp[k-1][i][j-1]+dp[k-1][i][j]*(k-2);

#include<cstdio>
using namespace std;
typedef long long LL;
LL dp[][][];
int main()
{
int T,n,l,r;
dp[][][]=;
for(int k=;k<=;k++)
for(int i=;i<=k;i++)
for(int j=;j+i-<=k;j++)
dp[k][i][j]=dp[k-][i-][j]+dp[k-][i][j-]+dp[k-][i][j]*(k-);
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&l,&r);
printf("%lld\n",dp[n][l][r]);
}
}