常州集训第8day

Today学习了动态规划课件如下：动态规划1
代码如下：
动态规划2

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, a[N];
int dp[N][4][2];
int main() {
    freopen("fruit.in", "r", stdin);
    freopen("fruit.out", "w", stdout)
    ;
    memset(dp, -0x3f3f3f3f, sizeof(dp));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= 3; ++j) {
            dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]);
            dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1] + a[i]);
            if (j >= 1)
                dp[i][j][1] = max(dp[i][j][1],
                                  max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + a[i]);
        }
    }
    printf("%d\n", max(dp[n][3][0], dp[n][3][1]));
    return 0;
}

今天也是脱离了爆零的命运。
Step in step