首页 > 代码库 > UVa 1638 Pole Arrangement

UVa 1638 Pole Arrangement

2024-08-13 08:22:45   217人阅读

 

递推。

设f[柱子数量][从左边能看到的数量][从右边能看到的数量]=方案数

假设2~i高度的柱子都已经安排好，现在要插入高度为1的柱子。若它放在最左边，左边可见数量+1，放在最右边，右边可见数量+1，放在中间（有i-2个可能位置），左右可见数量不变。

递推完一个高度i时，假设把所有在场的柱子都拔高1单位高度，此时方案数不变，再加一个高度为1的柱子进去……

 

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 const int mxn=30;10 LL f[mxn][mxn][mxn];11 void init(){12     int i,j,k;//有i个方块，从左边看能看到j个，从右边看能看到k个13     f[1][1][1]=1;14     for(i=1;i<=20;i++){15         for(j=1;j<=20;j++){16             for(k=1;k<=20;k++){17                 f[i][j][k]+=f[i-1][j][k]*(i-2)+f[i-1][j-1][k]+f[i-1][j][k-1];18             }19         }20     }21 }22 int n,l,r;23 int main(){24     init();25     int T;26     scanf("%d",&T);27     while(T--){28         scanf("%d%d%d",&n,&l,&r);29         printf("%lld\n",f[n][l][r]);30     }31     return 0;32 }

 

UVa 1638 Pole Arrangement


联系
我们