2021CCPC Xinjiang race-B

Title Link

This is a DP topic, but most of the time I wrote it as a greedy topic The result is that no matter how you write it, there are always cases that are not considered, and the code complexity of taking all cases into account is amazing. After the game, the teammates saw a principle somewhere: the topics that can be written with DP should be written with DP as much as possible.

The state selection of this question is very awkward. The first idea after reading the question is to take the optimal solution obtained in the previous n days as the state, but the selection of the previous days will have an impact on the selection of the following days. Moreover, the optimal solution in the previous n days is not necessarily greater than the optimal solution in the previous n-1 days. After calculating dp, you have to find the maximum value. Not impossible to write, but the code will be more complex.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
long long a[100005], dp[300005];
int main()
{
    int n, m, d, i;
    long long res = 0;
    scanf("%d%d%d", &n, &d, &m);
    for (i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        if (a[i] <= m)
        {
            dp[i] += a[i];
            dp[i + 1] = max(dp[i + 1], dp[i]);
            if (dp[i] > res)
                res = dp[i];
            continue;
        }
        dp[i + 1] = max(dp[i + 1], dp[i]);
        dp[i] += a[i];
        if (i + d + 1 <= n)
            dp[i + d + 1] = max(dp[i + d + 1], dp[i]);
        if (dp[i] > res)
            res = dp[i];
    }
    printf("%lld\n", res);
    return 0;
}

 

Most people choose the state: the maximum damage they can do in the last i day. The state transition is also carried out from the last day. The upside down benefit is that when the damage of a day exceeds the limit and affects the following days, there is no need to modify other values, as long as the state of the following day is not transferred during the state transfer of this day.

The code processed in reverse order is difficult to understand anyway. First, a two-dimensional version of dp array is written: dp[0][i] indicates that the last n bits do not take the maximum value that can be obtained by the current bit, and dp[1][i] indicates that the last n bits take the maximum value that can be obtained by the current bit. It's not hard to write code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
long long dp[2][200005], a[200005];
int main()
{
    int n, m, d, i;
    scanf("%d%d%d", &n, &d, &m);
    for (i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (i = n; i > 0; i--)
    {
        dp[0][i] = max(dp[0][i + 1], dp[1][i + 1]);
        if (a[i] <= m)
            dp[1][i] = max(dp[0][i + 1], dp[1][i + 1]) + a[i];
        else
            dp[1][i] = a[i] + max(dp[0][i + d + 1], dp[1][i + d + 1]);
    }
    printf("%lld", max(dp[0][1], dp[1][1]));
    return 0;
}

Note: when the processed state is used, the corresponding dp[0] and dp[1] always appear at the same time, and only the maximum value is taken. So dp no matter whether you take it or not, you only need to save the maximum value, so you only need to open a one-dimensional array.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
long long dp[200005], a[200005];
int main()
{
    int n, m, d, i;
    scanf("%d%d%d", &n, &d, &m);
    for (i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (i = n; i > 0; i--)
    {
        if (a[i] <= m)
            dp[i] = a[i] + dp[i + 1];
        else
            dp[i] = max(dp[i + 1], dp[i + d + 1] + a[i]);
    }
    printf("%lld", dp[1]);
    return 0;
}

 

Added by burhankhan on Tue, 25 Jan 2022 02:18:38 +0200