【題意】：給出一個(gè)序列有n個(gè)元素，按左到右可以選出一些元素，如果當(dāng)前元素在偶數(shù)次選取則得到該分?jǐn)?shù)，否則扣去該分?jǐn)?shù)，可以跳過(guò)一些元素不選，問(wèn)最后可以得到的最大分?jǐn)?shù)為多少。

【題解】：剛開(kāi)始想到了O(n)的做法，后來(lái)又被自己推翻了，最后經(jīng)過(guò)仔細(xì)思考發(fā)現(xiàn)之前的想法是對(duì)的。
              狀態(tài)：
                  dp[i][0] 表示已經(jīng)考慮了前i個(gè)元素，且已經(jīng)拿了奇數(shù)個(gè)元素的最大分?jǐn)?shù)
                  dp[i][1] 表示已經(jīng)考慮了前i個(gè)元素，且已經(jīng)拿了偶數(shù)個(gè)元素的最大分?jǐn)?shù)
              轉(zhuǎn)移：
                  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 }