【题意】：给出一个序列有n个元素，按左到右可以选出一些元素，如果当前元素在偶数次选取则得到该分数，否则扣去该分数，可以跳过一些元素不选，问最后可以得到的最大分数为多少。
【题解】：刚开始想到了O(n)的做法，后来又被自己推翻了，最后经过仔细思考发现之前的想法是对的。
状态：
dp[i][0] 表示已经考虑了前i个元素，且已经拿了奇数个元素的最大分数
dp[i][1] 表示已经考虑了前i个元素，且已经拿了偶数个元素的最大分数
转移：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - val[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + val[i]);
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define maxn 150500
6 int dp[maxn][2];
7 int val[maxn];
8 int n;
9 int solve() {
10 dp[0][0] = dp[0][1] = 0;
11 for(int i = 1; i <= n; i++) {
12 dp[i][0] = max(dp[i-1][0], dp[i-1][1] - val[i]);
13 dp[i][1] = max(dp[i-1][1], dp[i-1][0] + val[i]);
14 }
15 return max(dp[n][0], dp[n][1]);
16 }
17
18 int main() {
19 while(~scanf("%d", &n)) {
20 for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
21 int ans = solve();
22 cout << ans << endl;
23 }
24 return 0;
25 }