P3080 [USACO13MAR]The Cow Run G/S 解答

---

目录

• • 题面

  • 题目分析

  • • • 分析

  • 复杂度

  • 代码

题面

题面传送门

---

题目分析

分析

对于每一个状态变量f[l][r]而言：

• 当前处于左边未被处理的状态（f[l][r][0]）可以通过以下两种方式之一得到：一种是将左端点向右移动一格并加上相应的变化量；另一种是将右端点向左移动一格并加上相应的变化量。
• 当前处于右边未被处理的状态（f[l][r][1]）也可以通过以下两种方式之一得到：一种是将左端点向右移动一格并加上相应的变化量；另一种是将右端点向左移动一格并加上相应的变化量。

其中，

• f[i][j][0] 表示在处理完区间i到j后，在左边尚未完成的状态；
• f[i][j][1] 表示在处理完区间i到j后，在右边尚未完成的状态。

我们把n个点拆成n+1个点，找到0点，设为c，令f[c][c][0]=f[c][c][1]=0,其他的都为0x3f。

我们下一步可选去i-1位置，则会转至f[i-1][j]；或者可选去j+1位置，则会转至f[i][j+1]。
对于每一个当前的状态$a[j]{,}来说,它可能位于左侧或者右侧,