2014
01-05

Bruce Force has gone to Las Vegas, the El Dorado for gamblers. He is interested especially in one betting game, where a machine forms a sequence of n numbers by drawing random numbers. Each player should estimate beforehand, how many increasing subsequences of length k will exist in the sequence of numbers.

Bruce doesn’t trust the Casino to count the number of increasing subsequences of length k correctly. He has asked you if you can solve this problem for him.

The input contains several test cases. The first line of each test case contains two numbers n and k (1 ≤ k ≤ n ≤ 100), where n is the length of the sequence drawn by the machine, and k is the desired length of the increasing subsequences. The following line contains n pairwise distinct integers ai (-10000 ≤ ai ≤ 10000 ), where ai is the ith number in the sequence drawn by the machine.

The last test case is followed by a line containing two zeros.

The input contains several test cases. The first line of each test case contains two numbers n and k (1 ≤ k ≤ n ≤ 100), where n is the length of the sequence drawn by the machine, and k is the desired length of the increasing subsequences. The following line contains n pairwise distinct integers ai (-10000 ≤ ai ≤ 10000 ), where ai is the ith number in the sequence drawn by the machine.

The last test case is followed by a line containing two zeros.

10 5
1 2 3 4 5 6 7 8 9 10
3 2
3 2 1
0 0

252
0

#include<stdio.h>
int main()
{
while(1)
{
__int64 dp[105][105]={0};__int64 l;
int n,m,i,j,k,a[105];

scanf("%d %d",&n,&m);
if(n==0&&m==0)
return 0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<=n;i++)
{
dp[i][1]=1;
}
for(i=2;i<=n;i++)//这里开始dp
{
for(j=2;j<=m;j++)
{
for(k=1;k<i;k++)
{
if(a[i]>a[k])
{
dp[i][j]+=dp[k][j-1];
}
}
}
}
l=0;
for(i=m;i<=n;i++)//将长度为m的所有值相加就是结果了
{
l+=dp[i][m];
}
printf("%I64d/n",l);
}
return 0;
}


1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。