小贝薅羊毛球解(已解决）

问题讨论区 普及段
1

2. 小贝薅羊毛

题目ID：15669必做题100分

最新提交：

Wrong Answer

10 分

历史最高：

Wrong Answer

10 分

时间限制: 1000ms

空间限制: 524288kB

题目描述

618 商品大促即将到来，又到了小贝薅羊毛的时间！

商品界面一共有 n 件商品，手机界面仅显示 连续 的 m 件商品，为了薅羊毛，小贝会把手机界面显示的商品 都买下来。每件商品都有一个幸福值 pi​，表示小贝买了这件商品之后会提升的幸福感。

但是小贝的手机出了点问题，商品页面 只能往下滑，不能往上滑。并且小贝是一个追求新鲜感的人，任何商品只会买一次。也就是说，每次购买商品时，页面中的商品都是之前没买过的。

小贝一共会薅 k 次羊毛，问：薅完羊毛之后小贝的幸福感最大是多少？

输入格式

第 1 行读入 3 个整数 n,m,k

第 2 行读入n 个数 1,2,…,p1​,p2​,…,pn​

1≤(×)≤50001≤(m×k)≤n≤5000，0≤1090≤pi​≤109

输出格式

输出 11 个整数，代表可以取到的最大值

样例输入1

5 2 1
1 2 3 4 5

样例输出1

9

样例输入2

7 1 3
2 10 7 18 5 33 0

样例输出2

61

code(WA)

#include<bits/stdc++.h>
using namespace std;
long long a[114514],sum[114514],n,m,t,ans;
int main(){
	scanf("%d%d%d",&n,&m,&t);
	for(long long i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	long long maxx=-0x3f3f3f3f;
	for(long long i=m;i<=n;i++){
		if(sum[i]-sum[i-m]>maxx){
			maxx=sum[i]-sum[i-m];
		}
	}
	ans+=maxx;
	t-=1;
	while(t--){
		long long ws=0;
		for(long long i=1;i<=n;i++){
			if(a[i]==0)continue;
			sum[ws+1]=sum[ws]+a[i];
			ws++;
		}
		long long maxx=-0x3f3f3f3f;
			for(long long i=m;i<=n;i++){
				if(sum[i]-sum[i-m]>maxx){
					maxx=sum[i]-sum[i-m];
				}
		}
		ans+=maxx;
	}
	cout<<ans;
	return 0;
}
1 个赞
2

图片
言语表达不了我的震惊

1 个赞
4

乱写的，勿当真

5

我来助你

6

改出来了

#include <bits/stdc++.h>

#define LL long long
#define for_(i, a, b) for (int i = (a); i <= (b); i++)
#define _for(i, a, b) for (int i = (a); i >= (b); i--)
#define read() freopen("a.in", "r", stdin)
#define out() freopen("a.out", "w", stdout)
#define N 100005
#define Mod int(1e9 + 7)

using namespace std;

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<LL> p(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }

    // 计算前缀和，方便快速计算区间和
    vector<LL> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        _______________;
    }

    // 动态规划数组
    vector<vector<ll>> dp(n + 1, vector<LL>(k + 1, -0x3f));
    __________ // 初始化

    for (int i = 1; i <= n; i++)
    {
        for (int j = _; j <= k; j++)
        {
            // 不选第 i 件商品
            __________________;

            // 选第 i 件商品作为第 j 个区间的结尾
            if (i >= m && j >= 1)
            {
                ___________________;
                __________________________;
            }
        }
    }

    // 输出结果
    cout << dp[n][k] << endl;

    return 0;
}

（核心代码，挖空了）
求解决方案
样例已过

7

这是DeepSeek写的吧（坐在你斜后方的我看到了T^T）

8

是的是的，呵呵 :sweat_smile:

9

666，Deepseek≠Deepseek

10

666盐都不盐了，我编的诶（……
真用了是吧

11

哎呀，被你猜到了

12

呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃