USACO 5.1.3 Musical Themes

中文题目
这题我是用dp做的,首先可以把相邻两个数的差算出来,比如说给一个数列1 2 4 7 8 2 3 5 8,那么得到一个新数列:1 2 3 1 -6 1 2 3,这个新数列是上面那个数列相邻两项的差.然后我们的任务就变成了在这个新数列中求一个子序列,至少有4个元素[这里是4=5-1],然后至少重复2次,求这样的子序列的最大长度.我的做法是这样的,下面是伪代码:
for i=1 to N
for j=i+1 to N
if(j<=f[i-1][j-1]+i+1)
continue;//保证不重叠
if(num[i]==num[j])//这里是转移的一个条件
f[i][j]=f[i-1][j-1]+1;
if(f[i][j]>max)//更新最大值
max=f[i][j]
if(max<4)//这里是考虑那个最短为5个note的条件
max=-1;
max++;
printf(max)
但是这样之后在本地你可以全部AC,但是一提交你就会得到一个#9的错误,爆内存了.因为这里你必须开5000*5000的内存,可是这已经远远超过了16M了,然后你会发现f[i][j]只与f[i-1]k有关,那么我们就可以只开成这样了f[2][5006],转移的时候变成这样就OK了,f[i%2][j]=f[(i-1)%2][j-1]+1,不过这里还有一点就是每次i循环那里必须清空将要算的那一个数组,不然又值残留在那里,会导致错误,由于一开始没有考虑这一点错了一次.这样的话程序就好写了,代码量也不大,不到100行.