2019.4.3 51Nod 1270 数组的最大代价

转载：https://blog.csdn.net/dannis_bh/article/details/52649922

dp[i][0]::=前i项构成的子问题中，当Ai=1时的最大代价
dp[i][1]::=前i项构成的子问题中，当Ai=Bi时的最大代价
我们可以想象，能够得到最大代价的序列肯定是需要每一步都取极端值的，这样才能尽可能让波动最大化。
递推关系：
dp[1][0] = dp[1][1] = 0
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + abs(1-B(i-1)))
dp[i][1] = max(dp[i-1][1] + abs(Bi-B(i-1)), dp[i-1][0] + abs(Bi-1))
因为递推关系只存在于相邻的两项之间，所以dp数组的规模可以限定在2*2之内。算法的时间复杂度就是O（n）。可见，这个算法是一个时间和空间上都很优秀的算法。动态规划赛高！

dp只需要2*2  空间也得到了极大的优化。

#include <stdio.h>
#include <stdlib.h>
 
#define MAX(x, y) (x)>(y) ? (x) : (y)
 
int main()
{
    int i, n, b[50000], dp[2][2];
 
    scanf("%d", &n);
    for(i=0;i<n;i++)
        scanf("%d", b+i);
 
    dp[0][0] = 0;
    dp[0][1] = 0;
 
    for(i=1;i<n;i++)
    {
        dp[i%2][0] = MAX(dp[(i-1)%2][0], dp[(i-1)%2][1] + abs(1-b[i-1]));
        dp[i%2][1] = MAX(dp[(i-1)%2][1] + abs(b[i]-b[i-1]), dp[(i-1)%2][0] + abs(1-b[i]));
    }
 
    printf("%d", MAX(dp[(n-1)%2][0], dp[(n-1)%2][1]));
 
    return 0;

}