m*****f
发帖数: 1243 | 1 You are given N blocks of height 1…N. In how many ways can you arrange
these blocks in a row such that when viewed from left you see only L blocks
(rest are hidden by taller blocks) and when seen from right you see only R
blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}. | m*****f
发帖数: 1243 | 2 验证下我的想法。如下：
左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
定x= L-1, y >= R-1,
假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
y = n-x-1
f(a,b) 可以用DP求出...
觉得有点繁琐, 有人有别的想法么 | u******p
发帖数: 13 | 3 honestly, i am not familiar with DP, to me, it might be easier if we
approach it by
1) finding the largest two values in the array of N, denoted as N_maxA and N
_maxB and (N_maxA>N_maxB).
2) place N_maxA and N_maxB at the R^th and (L-1)^th position. Note that you
can place it in the opposite way, by placing N_maxB and N_maxA at the L^th
and (R-1)^th position
3) assuming we go with the first arrangement, then we will have a sequence (
in increasing order) placed at the left of the N_maxA, and a s | s***t
发帖数: 49 | 4 Longest Increasing Subsequence
blocks
}
【在 m*****f 的大作中提到】
: You are given N blocks of height 1…N. In how many ways can you arrange
: these blocks in a row such that when viewed from left you see only L blocks
: (rest are hidden by taller blocks) and when seen from right you see only R
: blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
: while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
| m*****f
发帖数: 1243 | 5 sigh..不是让你求LIS...回帖不看帖吗
【在 s***t 的大作中提到】
: Longest Increasing Subsequence
:
: blocks
: }
| m*****f
发帖数: 1243 | 6 step 5 不对, 你确定了最高的两个, 并不能保证剩下的L-1/R-1个slot, 就是说MaxA左
边或者MaxB右边, 怎么放都一定100%排成L长或者R长的LIS. 矮的放在高的后面就看不
见了
N
you
(
【在 u******p 的大作中提到】
: honestly, i am not familiar with DP, to me, it might be easier if we
: approach it by
: 1) finding the largest two values in the array of N, denoted as N_maxA and N
: _maxB and (N_maxA>N_maxB).
: 2) place N_maxA and N_maxB at the R^th and (L-1)^th position. Note that you
: can place it in the opposite way, by placing N_maxB and N_maxA at the L^th
: and (R-1)^th position
: 3) assuming we go with the first arrangement, then we will have a sequence (
: in increasing order) placed at the left of the N_maxA, and a s
| k***e
发帖数: 556 | 7 是对的
我最爱的题目类型
希望被问到
L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x= L-1, y >= R-1,
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
| g*******y
发帖数: 1930 | 8 我觉得你做的不错呢
L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x= L-1, y >= R-1,
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
| m*****f
发帖数: 1243 | 9 就怕有什么trick没想到阿, 战战兢兢的
【在 g*******y 的大作中提到】
: 我觉得你做的不错呢
:
: L,
| g*******y
发帖数: 1930 | 10 trick估计就是在算f(a,b)那里，有好的方法，也有差一点的方法。
【在 m*****f 的大作中提到】
: 就怕有什么trick没想到阿, 战战兢兢的
| | | c***y
发帖数: 560 | 11 f(a,b)的递推式似乎不好搞啊, any clue here?
【在 g*******y 的大作中提到】
: trick估计就是在算f(a,b)那里，有好的方法，也有差一点的方法。
| b****j
发帖数: 78 | 12 错的吧？
4 1 2 3应该算是f(4, 3)中的一种吧，但是只能看到4
L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x= L-1, y >= R-1,
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
| g*******y
发帖数: 1930 | 13 我觉得他(她)的思路应该是对的，不过表述可能有些问题:
f(a,b)应该是：a个数，固定从一个方向看过去(比如左边)，能看到b个数，有多少种情
况的结果。
【在 b****j 的大作中提到】
: 错的吧？
: 4 1 2 3应该算是f(4, 3)中的一种吧，但是只能看到4
:
: L,
| m*****f
发帖数: 1243 | 14 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
这表述有问题? 我又没说什么左阿右阿的, 数列中最长递增子序列阿, 不从左边开始从
哪儿开始阿...
【在 g*******y 的大作中提到】
: 我觉得他(她)的思路应该是对的，不过表述可能有些问题:
: f(a,b)应该是：a个数，固定从一个方向看过去(比如左边)，能看到b个数，有多少种情
: 况的结果。
| c***y
发帖数: 560 | 15 赫赫，现在的问题是这个f(a,b)怎么求得到，似乎不太easy
就问这个f(a,b)的问题估计也很难
【在 m*****f 的大作中提到】
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
: 这表述有问题? 我又没说什么左阿右阿的, 数列中最长递增子序列阿, 不从左边开始从
: 哪儿开始阿...
| m*****f
发帖数: 1243 | 16 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
设最大的那个数最终位置为x, 显然b<=x<=a, 得
f(a,b) = f(a-1, b-1) (x=a的情况) + f(a-2, b-1)*(a-1) (x=a-1的情况, a位置可放
任一数) + f(a-3, b-1)*(a-1)*(a-2) (x=a-2, a, a-1位置可放任意数) ....
until...f(b-1, b-1) * (a-1) * (a-2) ...(a-b)
声明一个axb的数组, 显然
f(*,1) = 1
f(a, b) = 1 if a = b
f(a, b) = 0 if a < b
然后填满这个数组, 我刚才懒得写完, 现在就写完罢
当然, 求更好的方法...
【在 c***y 的大作中提到】
: 赫赫，现在的问题是这个f(a,b)怎么求得到，似乎不太easy
: 就问这个f(a,b)的问题估计也很难
| x***y
发帖数: 633 | 17 How about
f(a,b)=sum_{k=b-1}^{a-1} f(k,b-1)×P(a-1,a-1-k)
with the initial condition f(a,1)=(a-1)! with a>0
【在 c***y 的大作中提到】
: 赫赫，现在的问题是这个f(a,b)怎么求得到，似乎不太easy
: 就问这个f(a,b)的问题估计也很难
| b****j
发帖数: 78 | 18 不知道有没有解析的公式，写了个递推的：
#include
int N,L,R;
long long num[128][128];
int main() {
int i,j,k;
scanf("%d%d%d", &N, &L, &R);
num[1][1] = 1;
for (i=2;i<=N;++i)
for (j=i;j>=1;--j)
for (k=i-j+1;k>=1;--k)
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
printf("%lld\n", num[L][R]);
return 0;
}
blocks
}
【在 m*****f 的大作中提到】
: You are given N blocks of height 1…N. In how many ways can you arrange
: these blocks in a row such that when viewed from left you see only L blocks
: (rest are hidden by taller blocks) and when seen from right you see only R
: blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3}
: while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
| g*******y
发帖数: 1930 | 19 nice!
But I think you can further improve, if you combine your idea with mudhoof's
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
| k***e
发帖数: 556 | 20 why dont you just say the answer?
just not that to get f(n, l, r)
define a_ln means given n numbers that look from left we can see just l of
them
b_rn means given n numbers that look from right and we can see just r
then a_ln=b_ln
to get a_ln, decompose on the smallest element
a_ln=a_l-1 n-1 + (n-1)a_l n-1
for n numbers with L R as given, the total time would be max(L, R)n to get a
_ij
then f(n,L,R) can be represented as a_ln, b_rn as have done by some ppl
before
thus the total time is just max(
【在 g*******y 的大作中提到】
: nice!
: But I think you can further improve, if you combine your idea with mudhoof's
| | | b****j
发帖数: 78 | 21 I think his idea is wrong.
's
【在 g*******y 的大作中提到】
: nice!
: But I think you can further improve, if you combine your idea with mudhoof's
| g*******y
发帖数: 1930 | 22 那我来转述一遍:
n个blocks，最高那个假设在位置k上，
可能的情况数有:
C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)
f(i,j)代表：i个不同的blocks(block的具体长度不重要，重要的只是大小顺序)，从左
往右看，能看到j个，有多少种情况
用你的思路来算f(i,j),就只需要两重循环，降低了一个维度的时间复杂度
【在 b****j 的大作中提到】
: I think his idea is wrong.
:
: 's
| m*****f
发帖数: 1243 | 23 ...if you say someone is wrong, at least also explain why...
【在 b****j 的大作中提到】
: I think his idea is wrong.
:
: 's
| b****j
发帖数: 78 | 24 算f(i,j)是两重循环，那么算最终答案是几重循环？
【在 g*******y 的大作中提到】
: 那我来转述一遍:
: n个blocks，最高那个假设在位置k上，
: 可能的情况数有:
: C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)
: f(i,j)代表：i个不同的blocks(block的具体长度不重要，重要的只是大小顺序)，从左
: 往右看，能看到j个，有多少种情况
: 用你的思路来算f(i,j),就只需要两重循环，降低了一个维度的时间复杂度
| b****j
发帖数: 78 | 25 I explained before:
in your notation, f(a, b) means the number of permutations of a numbers with
the longest increasing subsequence length being b.
4 1 2 3 is one of the sequence for f(4, 3), but when looking from left, only
4 can be seen.
【在 m*****f 的大作中提到】
: ...if you say someone is wrong, at least also explain why...
| g*******y
发帖数: 1930 | 26 这两重循环是主要的
假设所有的f(i,j)都已经算出来并存下来了：
最后一步就是算C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)对k求和的复杂度，也就是O（n)吧
【在 b****j 的大作中提到】
: 算f(i,j)是两重循环，那么算最终答案是几重循环？
| b****j
发帖数: 78 | 27 了解了
n)吧
【在 g*******y 的大作中提到】
: 这两重循环是主要的
: 假设所有的f(i,j)都已经算出来并存下来了：
: 最后一步就是算C(n,k-1) * f(k-1,L-1) * f(n-k,R-1)对k求和的复杂度，也就是O（n)吧
| m*****f
发帖数: 1243 | 28 你说得对, notation写错了, f(a,b)应该是a个元素从左边看有b个的数目, 不是简单的LIS, 但是好像想法还是正确的.
前面小尾羊的评论没错, 我没注意到
with
only
【在 b****j 的大作中提到】
: I explained before:
: in your notation, f(a, b) means the number of permutations of a numbers with
: the longest increasing subsequence length being b.
: 4 1 2 3 is one of the sequence for f(4, 3), but when looking from left, only
: 4 can be seen.
| r****o
发帖数: 1950 | 29 这句是什么意思啊？
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
| r****o
发帖数: 1950 | 30 这句能解释一下吗？
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
| | | b****j
发帖数: 78 | 31 递推，从高到低一个一个的放，现在放第i个高的
如果它被放到最左边，从左边看可看到的就多了一个
如果它被放到最右边，从右边看可看到的就多了一个
否则放到中间有i-2种方法，这块不能被看到了
【在 r****o 的大作中提到】
: 这句是什么意思啊？
: num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
| c***y
发帖数: 560 | 32 I guess you want to say:
num[j][k] = num[j-1][k] * (i - 2) + num[j-1][k] + num[j-1][k-1];
~~ ~~
not
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
【在 b****j 的大作中提到】
: 递推，从高到低一个一个的放，现在放第i个高的
: 如果它被放到最左边，从左边看可看到的就多了一个
: 如果它被放到最右边，从右边看可看到的就多了一个
: 否则放到中间有i-2种方法，这块不能被看到了
| u**s
发帖数: 50 | 33 No, you haven't fully understood his codes.
He used a common trick to reuse the variable/save space.
【在 c***y 的大作中提到】
: I guess you want to say:
: num[j][k] = num[j-1][k] * (i - 2) + num[j-1][k] + num[j-1][k-1];
: ~~ ~~
: not
: num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
| c***y
发帖数: 560 | 34 if you think this way from another perspective:
f(a,b) can be constructed by either adding the lowest block (a-th) in either
the first or the other places based on existing (a-1) blocks, then
f(a,b) = f(a-1,b)*(a-1) + f(a-1, b-1)
this is the interative way for your method
【在 m*****f 的大作中提到】
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法
: 设最大的那个数最终位置为x, 显然b<=x<=a, 得
: f(a,b) = f(a-1, b-1) (x=a的情况) + f(a-2, b-1)*(a-1) (x=a-1的情况, a位置可放
: 任一数) + f(a-3, b-1)*(a-1)*(a-2) (x=a-2, a, a-1位置可放任意数) ....
: until...f(b-1, b-1) * (a-1) * (a-2) ...(a-b)
: 声明一个axb的数组, 显然
: f(*,1) = 1
: f(a, b) = 1 if a = b
: f(a, b) = 0 if a < b
: 然后填满这个数组, 我刚才懒得写完, 现在就写完罢
| b***e
发帖数: 1419 | 35 Some small improvement:
Instead of computing number of solutions, compute probability. Then you
don't have to compute the crap of C(n-1, x).
n-L,
【在 m*****f 的大作中提到】
: 验证下我的想法。如下：
: 左右两边必然看到最高block结束, 以最高点划分, 可以假设左边x个, 右边y个,可以假
: 定x= L-1, y >= R-1,
: 假设f(a,b)代表a个数的数列中有长度为b的最长递增子序列的排法, 所求解为
: sum (C(n-1,x)*f(x, L-1) * f(y, R-1)), 已知 L-1 <= x <= n-R, R-1 <= y <= n-L,
: y = n-x-1
: f(a,b) 可以用DP求出...
: 觉得有点繁琐, 有人有别的想法么
| r****o
发帖数: 1950 | 36 C(n-1,x)这里是什么意思阿，是组合数吗？
【在 b***e 的大作中提到】
: Some small improvement:
: Instead of computing number of solutions, compute probability. Then you
: don't have to compute the crap of C(n-1, x).
:
: n-L,
| z***e
发帖数: 5393 | 37 。。。。。
这个...呃...我觉得没超过高考的难度啊。。。。
基本上，你能看到的（先不管左右，假设从左边吧）就是已经sorted了，就好像小学体
育课上老师说“最高的L个站出来”----（剩下的无视）；然后把这L个排序。
在这L个中最矮的一个肯定在最左边，这个位置固定，剩下L-1个站好，中间留空位，很
好，现在还剩N-L个人，有L-2个空位，每个空位可以容纳0-（N-L)个人，这就是典型的
高考水准排列组合题：有K个抽屉，M个球，问有几种放球的方法... | e***l
发帖数: 710 | 38 楼上想法不对，空位放的人不能比前面紧挨的高，但可以比前面的前面高。怎么算这个
组合？再说还有右边看的限制。 | z***e
发帖数: 5393 | 39 你说“前面的前面”，是指首先选出的Top L个人么？如果空位的人比这个高，那么这
top L就选错了。
嗯...不过我这个不能解决右边看的问题，要再想想。
【在 e***l 的大作中提到】
: 楼上想法不对，空位放的人不能比前面紧挨的高，但可以比前面的前面高。怎么算这个
: 组合？再说还有右边看的限制。
| e***l
发帖数: 710 | 40 说说我的想法，设g(N,L,R)为最终所求，那么根据最高的block的位置i=(1...N)，有N
个情况。于是
g(N,L,R)=Σ C(N-1, i-1) * f(i-1,L-1) * f(N-i,R-1)
i=1,2...N
其中第一项C(n,r)是组合数记号，从n个里面选r个的选法，
第二项f(n,a)表示只考虑最高的左边那些block，用i-1个block摆出从左看，有L-1个
block可见的摆法。
第三项是从右看的情况，函数是同一个（因为对称）。
接下来再考虑f，同样根据最高的block的位置，f可以递归求得
f(N,L) = Σ f(i-1,L-1)
i=1,2...N
再有几个初始值就可以求出g，但是直接的解析式似乎很麻烦。。。
测试了几个例子基本正确，大家看看正确吗？
代码：
#include "stdafx.h"
//求x的阶乘
int factorial(int x){
if(x==0) return 1;
int r=1;
for(int i=1;i<=x;i++)
r=r*i;
return r;
}
//求组 | | | e***l
发帖数: 710 | | H****r
发帖数: 2801 | 42 当L+R==N+1时f(N,L,R)=C(N-1,L)
如果L+R 和 N 接近时可以节省一点。
int HoofNumber(int length, int numLeft, int numRight)
{
int result=0;
if (numLeft+numRight > length+1 || numLeft == 0 || numRight ==0)
{
return 0;
}
else if (numLeft+numRight == length+1)
{
result = Factorial(length-1) / (Factorial(numLeft-1) * Factorial(
length-numLeft));
return result;
}
else
{
result = (HoofNumber(length-1, numLeft-1, numRight)
+ HoofNumber(length-1 | d****n
发帖数: 233 | 43 My solutio for f(a, b):
f(a, b) = sum{(C(a-1,0)*f(a-1, b-1)*P(0,0), C(a-1, 1)*f(a-1-1, b-1)*P(1, 1),
C(a-1, 2)*f(a-1-2, b-1)*P(2,2), ..., C(a-1, i)*f(a-1-i, b-1)*P(i,i)}, i = a
-b;
P(i, i) is the permutation.
N
【在 e***l 的大作中提到】
: 说说我的想法，设g(N,L,R)为最终所求，那么根据最高的block的位置i=(1...N)，有N
: 个情况。于是
: g(N,L,R)=Σ C(N-1, i-1) * f(i-1,L-1) * f(N-i,R-1)
: i=1,2...N
: 其中第一项C(n,r)是组合数记号，从n个里面选r个的选法，
: 第二项f(n,a)表示只考虑最高的左边那些block，用i-1个block摆出从左看，有L-1个
: block可见的摆法。
: 第三项是从右看的情况，函数是同一个（因为对称）。
: 接下来再考虑f，同样根据最高的block的位置，f可以递归求得
: f(N,L) = Σ f(i-1,L-1)
| l******o
发帖数: 144 | 44 我认为这段程序是完全正确的。
不知道有没有解析的公式，写了个递推的：
#include
int N,L,R;
long long num[128][128];
int main() {
int i,j,k;
scanf("%d%d%d", &N, &L, &R);
num[1][1] = 1;
for (i=2;i<=N;++i)
for (j=i;j>=1;--j)
for (k=i-j+1;k>=1;--k)
num[j][k] = num[j][k] * (i - 2) + num[j-1][k] + num[j][k-1];
printf("%lld\n", num[L][R]);
return 0;
}
blocks
}
【在 b****j 的大作中提到】
: 不知道有没有解析的公式，写了个递推的：
: #include
: int N,L,R;
: long long num[128][128];
: int main() {
: int i,j,k;
: scanf("%d%d%d", &N, &L, &R);
: num[1][1] = 1;
: for (i=2;i<=N;++i)
: for (j=i;j>=1;--j)
| y*****i
发帖数: 727 | 45
从高到低递归，好办法，赞一个。
【在 b****j 的大作中提到】
: 递推，从高到低一个一个的放，现在放第i个高的
: 如果它被放到最左边，从左边看可看到的就多了一个
: 如果它被放到最右边，从右边看可看到的就多了一个
: 否则放到中间有i-2种方法，这块不能被看到了
| m*****g
发帖数: 226 | 46 想了一下。
这个是错的。
either
【在 c***y 的大作中提到】
: if you think this way from another perspective:
: f(a,b) can be constructed by either adding the lowest block (a-th) in either
: the first or the other places based on existing (a-1) blocks, then
: f(a,b) = f(a-1,b)*(a-1) + f(a-1, b-1)
: this is the interative way for your method
| l**i
发帖数: 8 | 47 我有一个想法不知道正确不正确，如果用f(N,L,R)代表我们要求的数，那么可以写一个
递归式子：
f(N,L,R)=f(N-1, L-1,R) + f(N-1,L,R-1)
想法是首先最大数N肯定是放在中间的某个地方使得满足L，R的条件，如果我们把N拿掉
的话整个序列就变成了N-1的序列的子问题。这时有两种情况，如果N-1处在原先N的左
边区域的话，那么剩下的序列(以N-1为中心)是个从左看有L-1个，从右看仍有R个的序
列，这就是等号右边第一项，第2项同样道理是当N-1在N右边区域的情况。当然还要有
一些初始条件，最简单的f(1,1,1)=1,可能还需要其他的我没有再多想。不知道这个解
法行不行。 |
|
