|
|
Posted on 2008-09-09 11:15 Hero 阅读(89) 评论(0) 编辑 收藏 引用 所属分类: 代码如诗－－ACM
1 /*
2 ID: wangzha4
3 LANG: C++
4 TASK: theme
5 */
6
7 /*
8 Executing
9 Test 1: TEST OK [0.000 secs, 2756 KB]
10 Test 2: TEST OK [0.000 secs, 2756 KB]
11 Test 3: TEST OK [0.000 secs, 2756 KB]
12 Test 4: TEST OK [0.000 secs, 2756 KB]
13 Test 5: TEST OK [0.011 secs, 2752 KB]
14 Test 6: TEST OK [0.011 secs, 2752 KB]
15 Test 7: TEST OK [0.011 secs, 2752 KB]
16 Test 8: TEST OK [0.011 secs, 2752 KB]
17 Test 9: TEST OK [0.022 secs, 2756 KB]
18 Test 10: TEST OK [0.000 secs, 2752 KB]
19 Test 11: TEST OK [0.065 secs, 2752 KB]
20 Test 12: TEST OK [0.054 secs, 2756 KB]
21 Test 13: TEST OK [0.076 secs, 2756 KB]
22 Test 14: TEST OK [0.086 secs, 2756 KB]
23 Test 15: TEST OK [0.065 secs, 2756 KB]
24 */
25 #include <stdio.h>
26 #include <string.h>
27 #include <stdlib.h>
28
29 const int size = 5500 ;
30 int data[size] ;
31 int count[size] ;
32
33 int inn ;
34 int out ;
35
36 void input()
37 {
38 for( int i=0; i<inn; i++ ) scanf( "%d", &data[i] ) ;
39
40 for( int i=inn-1; i>=1; i-- )
41 {
42 data[i] = data[i] - data[i-1] ;
43 }
44 }
45
46 void process()
47 {
48 memset( count, 0, sizeof(count) ) ;
49
50 int out = 0 ; int outlen ; int outposi ;
51 for( int len=inn; len>=4; len-- )
52 {//枚举长度
53 //memset( count, 0, sizeof(count) ) ;
54
55 for( int sn=1; sn+len<inn; sn++ )
56 {//枚举起点
57 if( data[sn] == data[sn+len] )
58 {
59 if( count[sn+len-1] < len-1 )//同一主题不能重叠出现
60 {//长度不能大于等于枚举的len
61 count[sn+len] = count[sn+len-1] + 1 ;
62 if( count[sn+len] > out ) out = count[sn+len] ;
63
64 if( out == len-1 ) goto final ;
65 }
66 }
67 else
68 {
69 count[sn+len] = 0 ;
70 }
71 }
72 }
73 final:
74 {
75 if( out < 4 ) printf( "0\n" ) ;
76 else printf( "%d\n", out+1 ) ;
77 }
78 }
79
80 int main()
81 {
82 //freopen( "in.txt", "r", stdin ) ;
83
84 freopen( "theme.in", "r", stdin ) ;
85 freopen( "theme.out","w",stdout ) ;
86
87 while( scanf( "%d", &inn ) != EOF )
88 {
89 input() ;
90
91 process() ;
92
93 //output() ;
94 }
95
96 return 0 ;
97 }
|