摘要
Title: 2931. 糖果街进阶版
Tag: 树状数组、dp
Memory Limit: 64 MB
Time Limit: 1000 ms

2931. 糖果街进阶版

题意

略
思路

dp求最大值，dp[i]表示，在1~i中，且吃了i的糖果数量
那么 dp[i] = max(dp[1], dp[2], … , dp[i - k - 1]) + a[i]
max操作可以用树状数组求前缀最大值优化

代码

python 代码超时

#include <bits/stdc++.h>
using namespace std;
#define int long long

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 5e5 + 10, INF = 0x3f3f3f3f;

#define lowbit(x) ((x) & -(x))

int a[N], tree[N], n, k, dp[N];
void add(int x, int d)
{
    while(x <= n){
        tree[x] = max(tree[x], d);
        x += lowbit(x);
    }
}
int query(int x)
{
    int sum = 0;
    while(x > 0){
        sum = max(sum, tree[x]);
        x -= lowbit(x);
    }
    return sum;
}


signed main()
{
    IOS;
    cin >> n >> k;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    int ans = 0;
    for(int i = 1; i <= n; ++ i){
        if(i - k > 1){
            dp[i] = query(i - k - 1) + a[i];
        }
        else dp[i] = a[i];
        add(i, dp[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}

2931. 糖果街进阶版

题意

思路

代码