shunfurh
编程介的小学生
2019-05-21 13:47
采纳率: 92.7%
浏览 176

求出删掉最多数字的最少步数,怎么利用C语言程序编写代码的具体的方式来实现的

Problem Description
众所周知,度度熊喜欢的字符只有两个:B 和D。

今天,它发明了一个游戏:D游戏。

度度熊的英文并不是很高明,所以这里的D,没什么高深的含义,只是代指等差数列(等差数列百科)中的公差D。

这个游戏是这样的,首先度度熊拥有一个公差集合{D},然后它依次写下N个数字排成一行。游戏规则很简单:

1.在当前剩下的有序数组中选择X(X≥2) 个连续数字;

2.检查1 选择的X个数字是否构成等差数列,且公差 d∈{D};

3.如果2满足,可以在数组中删除这X个数字;

4.重复 1−3 步,直到无法删除更多数字。
度度熊最多能删掉多少个数字,如果它足够聪明的话?

为了挑战自己,度度熊给D游戏多设了一个条件,Xmin和Xmax,在游戏的第一步,选出X个连续数字时,必须满足Xmin≤X≤Xmax。它称这个游戏为D++游戏。

同时精益求精的度度熊还希望知道删掉最多数字的最少步数。

Input
第一行为T,表示输入数据组数。

每组数据以四个整数 N,M,Xmin,Xmax 开始 。接着的一行包括 N 个整数,表示排成一行的有序数组 Ai。接下来的一行是 M 个整数,即给定的公差集合 Di。

1≤T≤100

1≤N,M≤32

2≤Xmin≤Xmax≤16

−1 000 000 000≤Ai,Di≤1 000 000 000

Output
对第i组数据,输出

Case #i:

然后输出一行,为最多能删掉的数字和完成这个目标的最小步数,用空格隔开。

Sample Input
3
3 1 2 2
1 2 3
1
3 1 2 3
1 2 3
1
4 2 2 4
1 3 4 3
1 2

Sample Output
Case #1:
2 1
Case #2:
3 1
Case #3:
4 2

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

相关推荐