USACO Music Theme

最近几天生病在家，因此做题速度略有上升。

这道题有两种思路：
1、枚举最长theme长度，然后寻找是否存在。可以用二分提升速度
2、动态规划
先说第一种吧。先处理出一个diff数组，diff[i] = note[i + 1] - note[i]，那么如果存在长度为n的，中间至少间隔1个元素的diff子串，那么就有长度为n+1的theme。所以就有了下面的代码。

C语言: 高亮代码由发芽网提供

01 /*
02 LANG:C
03 ID:niat8181
04 PROB:theme
05 */
06
07 #include <stdio.h>
08 #include <stdlib.h>
09 #include <string.h>
10
11 int note[5050];
12 int diff[5050];
13 long diff_sum[5050];   //for qiuckness in comparison
14 int n;
15
16 int find(int len)
17 {
18     int i,j;
19     int t;
20     for(i = 0;i <= n - 2 * len;i ++)
21     {
22         t = diff_sum[i + len] - diff_sum[i];
23         for(j = i + len;j < n - len;j ++)
24             if(diff_sum[j + len] - diff_sum[j] == t && memcmp(diff + i,diff + j,len * sizeof(int)) == 0)        return 1;
25     }
26     return 0;
27 }
28
29 int main()
30 {
31     freopen("theme.in","r",stdin);
32     freopen("theme.out","w",stdout);
33     scanf("%d\n",&n);
34     int i;
35     for(i = 0;i < n;i ++)
36         scanf("%d",&note[i]);
37     for(i = 0;i < n - 1;i ++)
38         diff[i] = note[i + 1] - note[i];
39     diff_sum[0] = 0;
40     for(i = 0;i < n - 1;i ++)
41         diff_sum[i + 1] = diff_sum[i] + diff[i];
42    
43     int l,r,mid;
44     r = n / 2 - 1;
45     l = 3;
46     while(l < r)  //二分
47     {
48         mid = (l + r + 1) / 2;
49         if(find(mid))
50             l = mid;
51         else
52             r = mid - 1;
53     }
54     if(l >= 4)    printf("%d\n",l + 1);   //there is a theme
55     else printf("0\n");   //no theme exists
56     return 0;
57 }

现在说动态规划的。话说俺好久没写动态规划题目了，思路没有以前那么敏捷。这个题目可以说是最长公共子串（我觉得有必要翻一下算法导论额）的改版把。
用len[i][j]表示分别以note[i],note[j]开头的乐曲的最长相似长度。那么:
len[i][j] = len[i + 1][j + 1] + 1
当note[i] - note[j] == note[i + 1] - note[j + 1]（即可以连接成一个更长的theme）；
否则len[i][j] = 1(自身长度)

读者是否注意到，这个动态规划形式是二维的，5000*5000的int数组需要约50M空间。那么，就此放弃动态规划吗？

在状态转移方程中可以发现，len[i][j]仅和len[i+1][j+1]有关系。这样，一维数组就可以了。USACO的解答里甚至只用一个变量就足矣了。具体实施请看代码：

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04
05 int note[5050];
06
07 int main()
08 {
09     freopen("theme.in","r",stdin);
10     freopen("theme.out","w",stdout);
11     int N,i,d;
12     int len;
13     int maxlen = 0;
14     scanf("%d\n",&N);
15     for(i = 0;i < N;i ++)
16         scanf("%d",&note[i]);
17     for(d = 1;d < N;d ++)
18     {
19         len = 1;
20         for(i = N - d - 2;i >= 0;i --)
21         {
22             if(note[i] - note[i + d] == note[i + 1] - note[i + d + 1])
23                 len ++;
24             else
25                 len = 1;
26             if(len > d)    len = d;   //themes do not overlap, careful here
27             if(maxlen < len)    maxlen = len;   //compare while computing
28         }
29     }
30     if(maxlen >= 5)
31         printf("%d\n",maxlen);
32     else
33         printf("0\n");   //no theme found
34     return 0;
35 }