发布于 2014-10-17 07:35:32 | 307 次阅读 | 评论: 0 | 来源: 网友投递
谷歌(Google)搜索引擎
Google公司（中文译名：谷歌），是一家美国的跨国科技企业，致力于互联网搜索、云计算、广告技术等领域，开发并提供大量基于互联网的产品与服务，其主要利润来自于AdWords等广告服务。
Problem C. Card Game
Confused? Read the quick-start guide.
Small input
9 points
Solve C-small
You may try multiple times, with penalties for wrong submissions.
Large input
17 points
You must solve the small input first.
You have 8 minutes to solve 1 input file. (Judged after contest.)
Problem
Bob is fond of playing cards. On his birthday party, his best friend Alice gave him a set of cards.
There are N cards and each card contains an integer number. He put the cards from left to right on a desk and wants to discard some of them. Before he discards any cards, he will choose a number K. At each time, he always chooses 3 adjacent cards to discard, and we assume that the numbers on each card from left to right are a, b and c. Bob guarantees that
c - b = b - a = K
Bob want to know what is the smallest number of cards he can be left with at the end. If he ever has a choice of which cards to discard, he chooses the cards that will leave him with the fewest cards at the end.
Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test cases contains two lines. The first line of each test case contains two integers: the number of cards N and the number K Bob chooses. The second line contains N integers a1, a2, ..., aN the numbers on the cards from left to right.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the smallest number of cards Bob can be left with after he has discarded everything he can.
Limits
1 ≤ T ≤ 100.
1 ≤ ai ≤ 106(1 ≤ i ≤ N).
1 ≤ N ≤ 100.
Small dataset
K = 0.
Large dataset
1 ≤ K ≤ 106.
Sample
Input
Output
2
6 0
4 4 3 3 3 4
5 1
3 1 2 3 4
Case #1: 0
Case #2: 2
使用记忆化搜索：f[i][j]表示i到j的结果