URAL 1346 Intervals of Monotonicity

这个题直接看了Nocow上的代码..
很简单的DP解法..因为之前也遇到过类似的题目没有A掉, 抄完代码也没深入去想就不了了之..
这样是不对的..于是在这题的DP解法上好好想了想..

分析
..:
先说状态转移:

d[x][w] - x位置的数被分为单增(w=1)或分为单减(w=0)时的最小段数
d[x][w]=d[x-1][w], if no turning
            =min(d[x-1][0]+d[x-1][1])+1, if a turning encountered

伪代码
..:
d[a][0]=1;
d[b][1]=1;
for i from a to b:
  if F[i]>F[i-1]:
    d[i][0]=min(d[i-1][0], d[i-1][1])+1;
  else
    d[i][0]=d[i-1][0]
  if F[i]<F[i-1]:
    d[i][1]=min(d[i-1][0], d[i-1][1])+2;
  else
    d[i][1]=d[i-1][1]

答案就是min(d[b][0], d[b][1])

什么乱起八糟的呐这是..
对区间上的每一个拐点, 我们可以把他归为之前的结尾, 或之后的起点, 也就是说..
1 2 3 4 5 4 3
F[i]=4<F[i-1]=5, 拐点来了..那么i-1既可以是起点, 又可以是终点, 如下:
1 2 3 4 | 5 4 3
1 2 3 4 5 | 4 3

完了..