Pokémon Army (easy version)
给出n个数 让你找到一个子序列$a_{j1}-a_{j2}+a_{j3}-a_{j4}+a_{j5}… …$和最大。
其实很快就想到过dp[i][2]记录前i个数两种状态结尾的最大值,不过没细想下去。
dp[i][1]表示前i个数以减号结尾的最大值,dp[i][0]表示前i个数以加号结尾的最大值
先处理出dp[i][0]为前i个数的最大值(也就是只选最大值以加号结尾)
然后有四种状态转移:
$dp[i][0]=max(dp[i][0],dp[i-1][0])$
$dp[i][0]=max(dp[i][0],dp[i-1][1]+a[i])$
$dp[i][1]=max(dp[i-1][1],dp[i][1])$
$dp[i][1]=max(dp[i-1][1],dp[i-1][0]-a[i])$
其中,因为dp[i][1]全为0,因此第三种可以省略。
1 | long long a[300010]; |