a[i] : input data
b[i] : 前i 个 元素的且经历奇数步的最高值
c【i】:前i 个 元素的且经历偶数步的最高值
则 根据b【i】   c【i】  有没有用到a【i】分类即可
  
b[i]=max(b[i-1],c[i-1]+a[i])
c[i]=max(c[i-1],b[i-1]-a[i])


可用两个变量代替b【i】c【i】。显然结果就是b【n】
菜鸟只能想这么多了，希望大家多多发言，要不然偶这么多题不会做怎么办啊

• Re:做了一天，终于在pku上做出了一道！发狂中！DP o （n） 附个人思路 (22) sw81500345 2011-10-14 23:16:23