题解：CF788A Functions again

· · 题解

CF788A 题目传送门

题目大意

定义一个函数，函数如下：f(l,r) = \sum\limits_{i = l}^{r - 1 }|a_i−a_{i+1}| \cdot (−1)^{i−l}，而 1 \leq l \leq r \leq n，其中 n 是数组 a 的大小，|x| 表示 x 的绝对值。现在给你一个函数，请取恰当的 l,r 使 f 值最大，并输出最大的 f 值。

解决思路

直接考虑动态规划，令 f_{i,0} 表示以 i 为结尾，第 i 位为 + 号；令 f_{i,1} 表示以 i 为结尾，第 i 位为 - 号。然后通过计算两个相邻的数的差值，存入数组 dp，随后用得到的状态转移方程求出最大值。

f[i][0] = max(dp[i], f[i - 1][1] + dp[i]);
f[i][1] = max(0ll, f[i - 1][0] - dp[i]);
//状态转移方程求最大值

最后再来一重循环求答案的最大值即可。

注意事项

## 代码展示 ```cpp #include <iostream> #define ll long long //不开long long见祖宗 using namespace std; const int N = 1e5 + 10; ll n, a[N], dp[N]; ll f[N][2], ans; //f[i][j]表示以i为结尾并且第i位的符号为j int main() { scanf("%lld", &n);//建议scanf,更快 for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); for(int i = 1; i <= n; i++) dp[i] = abs(a[i] - a[i + 1]);//简化公式，加快速度 for(int i = 1; i <= n; i++) { f[i][0] = max(dp[i], f[i - 1][1] + dp[i]); f[i][1] = max(0ll, f[i - 1][0] - dp[i]); //状态转移方程求最大值 } for(int i = 1; i < n; i++) //求最大值 ans = max(max(f[i][0], f[i][1]), ans); printf("%lld\n", ans);//建议printf,更快 return 0; } ```