Problem B. sophistry

NC229641. Problem B. sophistry

描述

In Xiao K's QQ group, Xiao T always gets weird and weird.

Xiao T will speak in the group for $n$ days, and xiao K has an anger value of $m$ .

Xiao T has an ability value every day, and the ability value on day $i$ is $a_i$ . Every day, Xiao T will choose whether to laugh at Xiao K. If Xiao T chooses to laugh at Xiao K on day $i$ , Xiao K will be hurt by $a_i$ from Xiao T. On this basis, if Xiao T's ability value $a_i$ exceeds Xiao K's anger value $m$ , Xiao K will be furious and ban Xiao T for $d$ days. That is to say, in $i+1, i+2, ..., \min(i+d, n)$ days, Xiao T will be banned.

Now, Xiao T wants to maximize the damage to Xiao K, but Xiao T is too bad to solve this problem, so he found you. hope you can help him solve this problem. You only need to find out the maximum damage caused by Xiao T to Xiao K.

输入描述

The first line contains three positive integers 

The second line contains  positive integers 。

， ，

输出描述

Only one number per line is output, indicating the biggest damage caused by Xiao T to Xiao K。

示例1

输入:

5 2 11
8 10 15 23 5

输出:

示例2

输入:

20 2 16
20 5 8 2 18 16 2 16 16 1 5 16 2 13 6 16 4 17 21 7

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3 解法, 执行用时: 136ms, 内存消耗: 18848K, 提交时间: 2023-05-07 16:43:14

from sys import *
n,d,m = map(int,stdin.readline().split())
l = n+n+10
ls = [0] * l
ls[1:n+1] = map(int,stdin.readline().split())
dp = [0] * l
for i in range(n,0,-1):
    if ls[i] > m:
        dp[i] = max(dp[i+1],dp[i+d+1]+ls[i])
    else:
        dp[i] = ls[i]+dp[i+1]
print(dp[1])

C++(clang++ 11.0.1) 解法, 执行用时: 38ms, 内存消耗: 1944K, 提交时间: 2023-03-25 13:54:13

#include<iostream>
using namespace std;
int n,d;
long long k,a[100005],f[200005];
int main(){
	cin>>n>>d>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=n;i>0;i--){
		if(a[i]<=k)f[i]+=a[i]+f[i+1];
		else f[i]=max(f[i+1],a[i]+f[i+d+1]);
		
	}
	cout<<f[1];
	return 0;
}

上一题

下一题

详情