贪心观察+DP决策。
首先需要观察到一个结论：分割后的每一段肯定是单调增或者单调减的。
然后可以根据dp来决策如何分割价值最多。
dp[i][0]表示放完第i个，最后一段是递减的情况下的最大价值
dp[i][1]表示放完第i个，最后一段是递增的情况下的最大价值
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn=1e6+10; long long dp[maxn][2]; long long a[maxn]; int n; int main() { scanf("%d",&n); a[0]=0; dp[1][1]=dp[1][0]=0; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=2;i<=n;i++) { if(a[i]>a[i-1]) { dp[i][1]=max(dp[i-1][1]+a[i]-a[i-1],dp[i-1][0]); dp[i][0]=max(dp[i-1][0],dp[i-1][1]); } else if(a[i]<a[i-1]) { dp[i][0]=max(dp[i-1][0]+a[i-1]-a[i],dp[i-1][1]); dp[i][1]=max(dp[i-1][0],dp[i-1][1]); } else { dp[i][1]=dp[i][0]=max(dp[i-1][0],dp[i-1][1]); } } printf("%lld\n",max(dp[n][1],dp[n][0])); return 0; }
原文：http://www.cnblogs.com/zufezzt/p/5484716.html