题解 P2858 【[USACO06FEB]奶牛零食Treats for the Cows】

Kdlyh · 2019-02-10 02:24:30 · 题解

由题意可知每次只能取两端的零食。这就可以看出来这是一道区间DP题。

我设计出了一个状态 :

• - 当时我就自以为是的推出了转移方程: - $f[l][r]=max(f[l+1][r]+a[l]*(r-l+1),f[l][r-1]+a[r]*(r-l+1))

  • 这个非常好理解(事先说一句这是错的)，[l,r]这个区间的最大值可以由[l+1,r]这个区间的最大值或[l,r-1]这个区间转移而来。 但是这个方程有一个明显的问题:拿该题的样例来说,f[1][5]是由1,5,2,3,4这个顺序得到的。而按照上面的转移方程的话，它只能由f[1][4]和f[2][5]转移而来，且这个转移默认了新加上去的那个数是最后一个。而f[1][4]的最大值是由1,2,3,4这个顺序得来的，用我这个方程转移的话f[1][5]的顺序为1,2,3,4,5,f[2][5]的最大值是由5,2,3,4这个顺序的来的，而用了我这个方程转移后f[1][5]的顺序为5,2,3,4,1。都没法的出正确的答案，而且可以看到由f[2][5]转移后的到的那个顺序还是错的！这一切的错误都得归咎与且这个转移默认了新加上去的那个数是最后一个。这个性质。我们可以发现无论是a[l]还是a[r]再转移后的顺序中都显然应该是第一个。

  • 那我们将转移方程修改成默认新加上去的这个数是第一个不就行了吗？

  • 通过上面一番推导的出的思路，我们继续设计转移方程:

  • 既然新加上去的数默认是第一个，转移时原来的区间的值得被修改。我们继续那上面那个例子原来f[2][5]的顺序是5,2,3,4，f[2][5]值则是由a[5]+a[2]*2+a[3]*3+a[4]*4这样得出的。而转移成f[1][5]后，因为默认新加上去的数是第一个。所以f[1][5]的顺序是1,5,2,3,4。而此时f[1][5]的值则是由a[1]+a[5]*2+a[2]*3+a[3]*4+a[4]*5的出的。很明显原来的f[2][5]和现在f[1][5]的算式是有关联的。我们用求f[1][5]的值的算式减去求f[2][5]的值的算式可得

    (a[1]+a[5]*2+a[2]*3+a[3]*4+a[4]*5)-(a[5]+a[2]*2+a[3]*3+a[4]*4) =a[1]+a[5]+a[2]+a[3]+a[4]

  ​ =a[1]+\sum_{i=1}^4a_i

  很明显这个\sum_{i=1}^4a_i我们可以通过前缀和预处理得到。

  那么我们就得到了新的转移方程:

  ​ f[i][j]=max(f[l+1][r]+(s[r]-s[l])+a[l],f[l][r-1]+(s[r-1]-s[l-1])+a[r])

  ​ s[i]=\sum_{j=1}^ia_j

  这样一来就可以愉快地CODE了