题目大意：Dima送给他女友N只兔子，编号1-n（n<=3000）,当给兔子喂食时，它们会产生joy值，joy的取值有三种状态：
1.当前兔子左右两边都没有已经喂过的兔子；
2.当前兔子左右两边有且仅有一边有已经喂过的兔子；
3.当前兔子左右两边的兔子均已喂过。（编号1，n的兔子显然无法满足）
现给出每只兔子三种状态下的joy值，希望你帮助Dima的女友有Inna选择某种喂食顺序，使得总的joy值最大，仅输出最大的joy值。

这个问题可以采用动态规划的方法来解决，为什么呢？
注意到，每只兔子选取的joy值仅与它左右两边的兔子的状态有关，当前兔子的状态也仅影响到它左右两边的兔子（-.-||好吧，这是显然的)
我们用f[i]来表示前i只兔子喂完时的最大joy值，但是i的状态跟i+1有关，我们应该如何表示呢？这里有个我觉得很巧妙的办法，就是我们先假设出i+1的状态进行求解。因此，我们增加一维，用f[i][0]表示喂食第i只兔子时第i+1只兔子还没有喂过,f[i][1]表示喂食第i只兔子时第i+1只兔子已经喂过了，这样我们就能很容易从f[i][]跟f[i-1][]得出喂食i时 i-1, i+1,处于的状态了。自然的就得到状态转移方程。

状态转移：
f[i][0] = max(f[i-1][0]+a[i][1], f[i-1][1]+a[i][0])
f[i][1] = max(f[i-1][0]+a[i][2], f[i-1][1]+a[i][1])

显然最后的答案就是f[n][0]
复杂度应该是O(N)吧

总结：感觉这道题目还是很有趣的（对我这种傻×来说）。可说到底这还是一道水题，虽然比赛的时候我看到题目就想到了DP，但显然DP能力太弱了（真的是跪到不行T^T），没有想出来给怎么表示状态，然后我选择了放弃思考。。。（提醒自己：可以放弃治疗，决不能放弃思考。说不定就想出来了）果然是智商问题，外加做过的题太少。。。最后是看了liympanda大神的代码,然后理解出来上面那堆东西，能力有限，写得不好望见谅。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include
#include
#include

using namespace std;

const int MN = 3200;

int a[MN][3] = {0};
int f[MN][2] = {0};
int n, ans;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", &a[i][0]);
    for (int i = 0; i < n; i++) scanf("%d", &a[i][1]);
    for (int i = 0; i < n; i++) scanf("%d", &a[i][2]);
    f[0][0] = a[0][0]; f[0][1] = a[0][1];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            f[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                 if (f[i - 1][k] + a[i][1 - k + j] > f[i][j])
                    f[i][j] = f[i - 1][k] + a[i][1 - k + j];
            }
        }
    }
    ans = f[n - 1][0];
    cout << ans << endl;
    return 0;
}