| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 4744 | Accepted: 1930 |
Description
Input
Output
Sample Input
2 9 1 2 2 2 2 3 3 3 1 1 1
Sample Output
Case 1: 29 Case 2: 1
题意：通过点击某一颜色消除相邻的所有的这种颜色，得分为len*len,求最大分；
http://wenku.baidu.com/view/d956d2f30b4c2e3f5627630b
分析：当看代码的时候却觉着原来就是这么简单
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 6 using namespace std; 7 struct box_segment 8 { 9 int color,len; 10 }; 11 box_segment segment[200]; 12 int score[200][200][200]; 13 int click_score(int start,int End,int extra_len) 14 { 15 if(score[start][End][extra_len] > 0) 16 return score[start][End][extra_len]; 17 int result; 18 result = segment[End].len + extra_len; 19 result = result * result; 20 if(start == End) 21 { 22 score[start][End][extra_len] = result; 23 return score[start][End][extra_len]; 24 } 25 result += click_score(start, End - 1, 0); 26 for(int i = End - 1; i >= start; i--) 27 { 28 if(segment[i].color != segment[End].color) 29 continue; 30 int temp = click_score(start, i, segment[End].len + extra_len) + click_score(i + 1, End - 1,0); 31 if(temp <= result) 32 continue; 33 result = temp; 34 break; 35 } 36 score[start][End][extra_len] = result; 37 return score[start][End][extra_len]; 38 } 39 int main() 40 { 41 int t,n,End; 42 int num = 0; 43 scanf("%d", &t); 44 while(t--) 45 { 46 End = 0; 47 scanf("%d", &n); 48 scanf("%d", &segment[End].color); 49 segment[End].len = 1; 50 for(int i = 1; i < n; i ++) 51 { 52 int color; 53 scanf("%d", &color); 54 if(color == segment[End].color) 55 segment[End].len++; 56 else 57 { 58 segment[++End].color = color; 59 segment[End].len = 1; 60 } 61 } 62 memset(score, 0, sizeof(score)); 63 printf("Case %d: %d\n", ++num,click_score(0, End, 0)); 64 } 65 return 0; 66 }
原文：http://www.cnblogs.com/zhaopAC/p/5067863.html
