发布于 2014-10-17 07:35:32 | 296 次阅读 | 评论: 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的结果

  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <iostream>  
  4. #include <algorithm>  
  5. using namespace std;  
  6. const int maxn = 110;  
  7. int dp[maxn][maxn] , a[maxn];  
  8. bool vis[maxn][maxn];  
  9. int N , K;  
  10. int dfs(int L,int R) {  
  11.     if(L > R) return 0;  
  12.     if(vis[L][R]) return dp[L][R];  
  13.     vis[L][R] = true;  
  14.     if(R-L+1 <= 2) return dp[L][R] = (R-L+1);  
  15.     int Min = R-L+1;  
  16.     for(int i=L;i<R;i++) {  
  17.         int tmp = dfs(L,i) + dfs(i+1,R);  
  18.         if(tmp < Min) Min = tmp;  
  19.     }  
  20.     int mid = R-2 , tmp = R-L+1;  
  21.     if(mid > L && dfs(mid,R) == 0) tmp = min(tmp,dfs(L,mid-1));  
  22.     mid = L+2;  
  23.     if(mid < R && dfs(L,mid) == 0) tmp = min(tmp,dfs(mid+1,R));  
  24.     Min = min(Min , tmp);  
  25.     for(int i=L+1;i<R;i++) {  
  26.         if(dfs(L+1,i-1)==0 && dfs(i+1,R-1)==0 && a[i]-a[L]==K && a[R]-a[i]==K) return dp[L][R] = 0;  
  27.     }  
  28.     return dp[L][R] = Min;  
  29. }  
  30. void debug() {  
  31.     for(int i=1;i<=N;i++)  
  32.     {  
  33.         for(int j=1;j<=N;j++) printf("%4d ",dp[i][j]);  
  34.         puts("");  
  35.     }  
  36. }  
  37. int main() {  
  38.     int T ,cas = 1;  
  39.     scanf("%d" , &T);  
  40.     while(T--) {  
  41.         scanf("%d%d" ,&N,&K);  
  42.         memset(vis,false,sizeof(vis));  
  43.         for(int i=1;i<=N;i++) scanf("%d" , &a[i]);  
  44.         int ans = dfs(1,N);  
  45.         printf("Case #%d: %d\n" , cas++ , ans);  
  46.         //debug();  
  47.     }  
  48.     return 0;  


最新网友评论  共有(0)条评论 发布评论 返回顶部

Copyright © 2007-2017 PHPERZ.COM All Rights Reserved   冀ICP备14009818号  版权声明  广告服务