单调增长的子序列的一个算法题,要求利用C语言的程序编写的思想来实现怎么做

Problem Description
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.

Input
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.

Output
For each test case, print one line with the number of increasing subsequences of length k that the input sequence contains. You may assume that the inputs are chosen in such a way that this number fits into a 64 bit signed integer .

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

Sample Output
252
0

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
【算法刷题】 最长单调子序列
子序列在原序列中可以是不连续的动态规划求解://时间复杂度   n*n//令c[i]表示:在a[0->i]中,当以a[i]为单调递增子序列最后一个元素时,所得最长单调递增子序列的长度。状态转移方程:c[0]=1;c[i]=max{1,c[j]+1}    a[j]<a[i]&&j<i;int LongestIncr(int X[], int n, int c[],...
利用链表的思想来实现list
class error(Exception): def __init__(self,message): super(error,self).__init__() self.message=message def __str__(self): return "out of range" class Node():#节点 def...
算法相关-最长单调子序列
用VC编写的控制台程序,用增量法求给定序列的最长单调子序列。
C语言编写的算法程序
C语言算法程序,详细描述各种算法,以及算法的过程。包含源文件。
这题用最长上升子序列的思想怎么做??(C 语言)
Preparing for CET 6 rnTime Limit:50MS Memory Limit:32768KrnDescription:rnrn英语6级就要开考了,可是Fatboy连单词都还没有背,这下可把他急坏了。于是他只好拿出单词册来,开始背单词。 背了一段时间后,Fatboy发现了一个背单词的高效方法。当把单词头尾相接串成一组单词后,可以一下子把串起来的所有单词都记住。比如:fatboy yard derv vivid ,这4个单词每个单词的头字母都与前一个单词的尾字母相同,那么Fatboy就可以一下子记住这4个单词。Fatboy拿着单词册,产生了一个疑问: “如果只串一次,我最多可以背多少单词呢?” 下面就请你编个程序来帮助他解决这个问题,记住:每个单词只能用一次,单词串接时单词出现的先后顺序必须和单词册中单词出现的先后顺序一样。如:假如单词册中单词出现的顺序是:12345 ,那么单词串接顺序不能是:5421或5134,而134则是一个合法串接。rnInput:rnrn每组数据第一行为数N(1≤N≤200),表示单词册里有多少个单词,紧接的N行按单词在单词册中出现顺序给出单词,输入文件以一个0表示结尾。rnOutput:rnrn对应每一组单词输出一个M,表示Fatboy最多可以记住多少单词。每个输出占一行。rnSample Input:rnrn4rnfatboy rnyard rnderv rnvividrn5rnfatboy rnyard rnderv rnvividrnuinquern2rnapplernorangern0rnSample Output:rnrn4rn4rn1
深搜算法:倒油/面向对象的思想来做
题目:有一位厨师要从盛12斤油(a桶)的桶中倒出6斤油来,可是手边只有盛8斤油(b桶)和盛5斤油(c桶)的两个桶,问如何操作才能将6斤取出来呢? 下面为JAVA实现代码: 主类: package cn.hncu.oil.dfs1; import cn.hncu.oil.common.Bucket; import cn.hnc...
C语言-算法题
腾讯算法面试题,50个台阶,一次可以上一个或两个台阶,一共有多少可能?  #include #include #include //腾讯面试题:有50个台阶,每次走一步或两步,有多少种可能 double go(int n){ if (n == 1){ return 1.0; }else if (n ==2){ return 2.0; }else{ return tx(n -
利用C语言编写的1602液晶程序
C语言编写的1602液晶程序,用以测试1602的各项指令功能。
C语言实现:最大的子序列和
最大的子序列和(1007.Maximum Subsequence Sum (25) | Programming Ability Test  https://www.patest.cn/contests/pat-a-practise/1007) 有一个包含K个整数{ N1, N2,..., NK }的序列。一个连续的子序列被定义为 { Ni, Ni+1, ..., Nj }(1 现在你需要找出最
求解最长单调子序列.
给定一个长度N的子序列,求出一个单调递增的最长子序列长度,子序列可以不连续。这道题我暂时只找到了O(N^2)复杂度的算法:可以把问题看作一个简单的DP问题。假设result[k]是代表以第k个元素作为结尾的某一个单调子序列的长度,那么对于第k+1个元素结尾的单调子序列,可以这样计算result[k+1]=max(1+result[i])wherearray[i]<array[k+1],ifrom0t
单调递增的子序列
方法一   转化为lcs最长公共字串  方法二    动态规划 方法三   数组+二分查找   方法一 对单调递增的子序列X排序得到子序列Y,然后求子序列X与子序列Y的最长公共字串   方法二  动态规划 1. 先准备一个数组b b[i]=1 2. b[i]=max(b[i],b[j]+1);        arr[j]&amp;lt;arr[i]   动态规划时间复杂度O(N^2)...
最长单调子序列例题
1. HDU 1025 Constructing Roads In JGShining's Kingdom Problem Description JGShining's kingdom consists of 2n(n is no more than 500,000) small cities which are located in two parallel lines. Half of...
c语言一道题 怎么做
rn六、平方和与立方和rnrnTime Limit:1000MS Memory Limit:65536KrnTotal Submit:85 Accepted:44rnrnDescriptionrnrn给定一段连续的整数的开头和结尾,求出他们中所有偶数的平方和以及所有奇数的立方和。rnrnInputrnrn输入一组数据,该组测试实例包含一行,由两个整数m(开头)和n(结尾)组成 (m <= n) ,m与n之间用空格隔开。rnrnOutputrnrn对于该组输入数据,输出一行,应包括两个整数x和y,分别表示该段连续的整数中所有偶数的平方和以及所有奇数的立方和,两数之间有一个空格,输出结果后换行。 rn你可以认为32位整数足以保存结果。 rnrnSample Inputrnrnrn1 3rn2 5rnSample Outputrnrnrn4 28rn20 152rnHintrnrn以上输入输出样例中有两组的测试数据rnrnSourcern下面是我做的 不知道哪里错rn#include rnint main()rnrn int b,c;rn scanf("%d %d",&b,&c);rn int a[c],i,s=0,d=0;rn for(i=b;i<=c;i++)rn a[i]=i;rn for(i=b;i<=c;i++)rn if[i]%2==0)rn s=s+a[i]*a[i];rn elsern d=d+a[i]*a[i]*a[i];rn printf("%d %d",s,d)rn return 0;rnrn
这道c语言题怎么做
Descriptionrnrn冰冰最近刚学了一个好玩的游戏,并为之兴奋,于是他天天找人陪他玩游戏,这个游戏就是传说中的“石头剪刀布”。 游戏规则是,出拳之前双方齐喊口令“石头、剪子、布”(或其他口令),然后在话音刚落时同时出拳。握紧的拳头代表“石头”,食指和中指伸出代表“剪子”, 五指伸开代表“布”。“石头”胜“剪子”,“剪子”胜“布”,而“布”又胜过“石头”。若两人出的是一样的,则为平局。 现在问题来了,由于玩的盘数太多,从小不太擅长数数的的他无法计算出他总共胜了几场,平了几场,输了几场,请好心的你帮帮他吧!!!rnrnInputrnrn输入第一行包含一个整数n(0 < n <= 1000),表示他一共进行了几轮游戏。接下来n行每行有两个数字i,j(i表示冰冰出的拳,j表示他对手出的拳,若值为0则表示出的是石头,若值为1则 表示出的是剪刀,若值为2则表示出的是布。我们保证i,j的值是0到2之间的整数)。rnrnOutputrnrn输出共有3行, 第一行输出一个整数表示冰冰一共赢了几轮的游戏; 第二行输出一个整数表示冰冰一共平了几轮的游戏; 第三行输出一个整数表示冰冰一共输了几轮的游戏。rnrnSample Inputrnrnrn3rn0 1rn0 0rn0 2rnSample Outputrnrnrn1rn1rn1rnHintrnrn以上输入输出样例中只有一组的测试数据rnrnSource
【算法题】排序子序列
查找数组拐点
【算法题】最长回文子序列
给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢? 输出需要删除的字符个数。 输入描述: 输入数据有多组,每组包含一个字符串s,且保证:1<=s.length<=1000. 输出描述: 对于每组数据,输出一个整数,代表最少需要删除的字符个数。 输入例子: abcda google 输
[GIS算法] 求单调链 - C语言实现
单调链:一个点序列在某个直线上投影如果是有序的,则认为此点序相对与该直线是一个单调链 【问题】找到任意点序列相对于Y轴的所有单调链 #include&amp;lt;stdio.h&amp;gt; typedef struct _POINT{ double x; double y; }POINT; // 求单调链 int GetLink(POINT *points, int n) { //两个两个判断 ...
PID算法程序C语言编写
PID算法程序 调试验证可以用 读者可以根据需要加以修改 以应用于各种控制领域 例如电机控制 温度控制
c语言编写的FxLMS算法程序
c语言编写的FxLMS算法程序
C语言编写的八皇后算法程序
C语言编写的八皇后算法程序, 使用了递归回溯方法.
C语言编写的各种算法程序
C语言程序190例.doc,C语言归并、选择、直接插入、希尔、冒泡、快速、堆排序与顺序、二分查找排序.docx,经典算法50例(绝对经典).doc,C语言算法100例.doc,C语言趣味程序设计编程百例精解.doc
利用C语言实现八数码算法
利用C语言实现八数码算法,源程序文件,人工智能课实验
C语言实现有关顺序表的算法题
1.已知A,B和C为三个元素值递增有序顺序表,要求对A作如下运算,删除既在B中出现又在C中出现的元素。 #include&amp;lt;stdlib.h&amp;gt; #include&amp;lt;stdio.h&amp;gt; #define MAXSIZE 100 typedef struct{ int len; int size; int *data; }sqlist; int insert(sqlist *...
c语言编写的停车场题
c语言的停车收费问题,是我自己写的。我是初学者还请多多指教
决策树实现算法C语言编写
决策树算法实现分类,采用c语言进行编写!能够进行MFC显示,结果比较好!
一个程序编写题
问题是这样的:编写一个程序,求解一元二次方程:a*x*x+b*x+c=0.参数a、b及c从命令行输入。rn然后我写的程序是rnrnpublic class a001rn rn public static void main(String []args)rn rn if(args.length!=3)rn rn System.out.println("Usage: java SolveQuadratic aCoef bCoef cCoef \nExample java a001 1 2 1");rn System.exit(-1);rn rn double a,b,c;rn double a=double.parseDouble(args[0]);rn if(Math.abs(a)0)rn rn System.out.println("The first answer "+(-b-Math.sqrt(d))/2*a);rn System.out.println("The second answer "+(-b+Math.sqrt(d))/2*a);rn rn elsern double e=(-b)/2*a;rn double f=Math.sqrt((-d)/2*a);rn System.out.println("The first answer "+e+"+"+f+"i");rn System.out.println("The second answer "+e+"-"+f+"i");rn rnrnrnrnrnrnrnrnrn然后提示说:double a=double.parseDouble(args[0]);double b=double.parsedouble(args[1]);double c=double.parsedouble(args[2]);这三句需要class,不知怎么解决。rn谢谢您的关注。rn
求一个简单的C语言算法题
找出所有六位数中满足下列条件的数字rnrn就是若在此6位数中相邻3个或3个以上数字相同,找出这些数,并显示出来。
求一个数组的最长的单调自增子序列(C代码实现)
题目: 给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱) 例如:给定一个长度为8的数组A{1,3,5,2,4,6,7,8},则其最长的单调递增子序列为{1,2,4,6,7,8},长度为6。 输入:数组,数组长度 输出:输出该数组最长递增子序列的长度 解题思想: 1、先对原始数组进行排序,原数组为{1,3,5,2,4,6,7
经典C语言算法题
经典C语言算法题 8皇后 高精度N! 解方程组 链表
C语言算法200题
C语言基础题库,喜欢学习的朋友可以下过去研究下,很不错的
c语言面试算法题
面试中遇到的算法题,不是算法的总结
一个C语言的题
char *format="%s,a=%d,b=%d\n";rnint a=1,b=10;rna+=b;rnprintf(format,"a+=b",a,b);rnrnrn这段程序运行的结果是什么为什么?rnrn谢谢大家帮忙!!!!!!!!!!!
最长公共子序列.(C语言编写) 算法
最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法最长公共子序列.(C语言编写) 算法
页面置换算法(C语言编写)
页面置换算法(C语言编写)模拟操作系统的页面置换算法(C语言编写),运行环境为vs2005
使用C语言实现一个闹钟, 怎么做?
Problem DescriptionrnAdvanced courses in computer science often include many interesting optimization problems. The following optimization problem is not advanced, nor is it particularly interesting. You are to write a program to determine the minimum number of buttons a person must push to set their alarm clock. Assume the alarm clock has 7 buttons – hour-up, hour-down, tens-minute-up, and tens-minute-down, ones-minute-up, ones-minute-down, and am/pm. For example, continuously pushing the hour-up button will cause hour digit to go through the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, …. Pushing the hour-down button will cause the sequence to go in the reverse order. Pushing the tens-minute-up buttons cycles tens minute digit through the numbers 0, 1, 2, 3, 4, 5, 0, 1, … Pushing the ones-minute-up button cycles the one digit through the numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, … Pushing the am/pm button causes toggles the am/pm indicator.rn rnrnInputrnThe first line of input will contain an integer indicating the number of problems that need to be processed. Each line will contain two times – the first one the current time and the second one the desired time. All times will have the format: 1 or 2-digit hour; followed by a colon; followed by a 2-digit minute; followed by “am” or “pm”. A single space will separate the two times.rn rnrnOutputrnYour program should produce one line of output for each problem using one of two formats: ”Going from 7:30am to 7:33am requires 3 pushes.” or “Going from 7:30am to 7:20am requires 1 push.”rn rnrnSample Inputrn6rn7:30am 7:30amrn7:30am 7:33amrn7:30am 7:20amrn7:30am 7:27amrn7:30am 7:30pmrn7:10am 7:50amrn rnrnSample OutputrnGoing from 7:30am to 7:30am requires 0 pushes.rnGoing from 7:30am to 7:33am requires 3 pushes.rnGoing from 7:30am to 7:20am requires 1 push.rnGoing from 7:30am to 7:27am requires 4 pushes.rnGoing from 7:30am to 7:30pm requires 1 push.rnGoing from 7:10am to 7:50am requires 2 pushes.
C语言编写的维吉尼亚算法
实现维吉尼亚加密算法。 任意输入密钥字符串(小于10),对任意输入明文串(小于50)加密解密。
C语言编写的万年历算法
这是用C语言编写的万年历算法,是当时的一个课程设计,做的应该没错误了
c语言编写的货郎担算法
c语言编写的货郎担算法,可以运行,大家参考参考
TDMA算法 C语言编写
有限元,有限差分,有限体积法离散的方程通常为三对角方程组,利用C语言编写的TDMA算法求解三对角方程组
数字三角形(C语言编写) 算法
数字三角形(C语言编写) 算法
相关热词 c#检测非法字符 c#双屏截图 c#中怎么关闭线程 c# 显示服务器上的图片 api嵌入窗口 c# c# 控制网页 c# encrypt c#微信网页版登录 c# login 居中 c# 考试软件