QQ扫一扫联系
拦截导弹
某国为了防御敌国的导弹袭击， 发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷： 虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。 某天， 雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段， 所以只有一套系统， 因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数） ， 计算这套系统最多能拦截多少导弹。
时间限制： 1000
内存限制： 65536
输入
第一行是一个整数 N（不超过 15） ， 表示导弹数。 第二行包含 N 个整数， 为导弹依次飞来的高度（雷达给出的高度数据是不大于 30000的正整数） 。
输出
一个整数， 表示最多能拦截的导弹数。
样例输入
8 389 207 155 300 299 170 158 65
样例输出
6
神奇的数列
一个正整数数列， 可以将它切割成若干个数据段， 每个数据段由值相同的相邻元素构成。 该数列的神奇之处在于， 每次切除一个数据段后，该数据段前后的元素自动连接在一起成为邻居。 例如从数列“2 8 9 77 6 9 4” 中切除数据段“7 7 ” 后， 余下的元素会构成数列“2 8 9 6 94”
请问若要将该数列切割成若干个数据段， 则至少会切出来几个数据段？
样例： 按下列顺序切割数列“2 8 9 7 7 6 9 4” ， 只要切割成 6 段
切割出“7 7” ， 余下 “2 8 9 6 9 4”
切割出 “6” ， 余下 “2 8 9 9 4”
切割出 “9 9” ， 余下 “2 8 4”
切割出 “2” ， 余下 “8 4”
切割出 “8” ， 余下 “4”
时间限制： 1000
内存限制： 65536
输入
第一行是一个整数， 示共有多少组测试数据。 每组测试数据的输入包括两行： 第一行是整数 N, N<=200,表示数列的长度， 第二行是 N 个正整数。
输出
每个测试案例的输出占一行， 是一个整数。 格式是： Case n: x n 是测试数据组编号， x 是答案
样例输入
2 8 2 8 9 7 7 6 9 4 16 2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9
样例输出
Case 1: 6 Case 2: 11
硬币
宇航员 Bob 有一天来到火星上， 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了， 一共有 n 种， 每种只有一个： 面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物， 想买来送给朋友 Alice， 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的， 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零， 只接受恰好 X 元。
时间限制： 1000
内存限制： 262144
输入
第一行包含两个正整数 n 和 x。 （1 <= n <= 200, 1 <= x <= 10000)
第二行从小到大为 n 个正整数 a1, a2, a3 … an （1 <= ai <= 10000)
输出
第一行是一个整数， 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值（从小到大排列） 。
样例输入
5 18 1 2 3 5 10
样例输出
2 5 10
提示
输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币， 则第一行输出 0， 第二行输出空行。
公共子序列
我们称序列 Z = < z1, z2, ..., zk >是序列 X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >， 使得对 j = 1, 2, ... ,k, 有xij = zj。 比如 Z = < a, b, f, c > 是 X = < a, b, c, f, b, c >的子序列。 现在给出两个序列 X 和 Y， 你的任务是找到 X 和 Y 的最大公共子序列， 也就是说要找到一个最长的序列 Z， 使得 Z 既是 X 的子序列也是 Y 的子序列。
时间限制： 3000
内存限制： 65536
输入
输入包括多组测试数据。 每组数据包括一行， 给出两个长度不超过200 的字符串， 表示两个序列。 两个字符串之间由若干个空格隔开。
输出
对每组输入数据， 输出一行， 给出两个序列的最大公共子序列的长度。
样例输入
abcfbc abfcab programming contest abcd mnp
样例输出
4 2 0
