n^2过?
查看原帖
n^2过?
812736
Wu_JL楼主2024/8/5 18:44
#include<bits/stdc++.h>
#define int long long
using namespace std;

#define rep(i , l , r) for(int i = (l); i <= (r); ++ i)
#define per(i , r , l) for(int i = (r); i >= (l); -- i)
int read(){
	int sum = 0 , f = 1;
	char ch = getchar();
	for(; !isdigit(ch) ; ch = getchar()) if(ch == '-') f = -f;
	for(; isdigit(ch) ; ch = getchar()) sum = (sum << 1) + (sum << 3) + (ch ^ 48);
	return sum * f;
}
const int N = 1e5 + 10;
int n , m , a[N] , dp[N] ,ans = 1e15,sum;
signed main(){
	cin >> n >> m;
	rep(i , 1 , n) a[i] = read() , sum += a[i];
	rep(i , 1 , n){
		int tmp = 1e15;
		rep(j , max(0ll , i-m-1) , i-1)tmp = min(tmp , dp[j]);
		dp[i] = tmp + a[i];
//		cout << dp[i] << " ";
	}
	rep(i ,  n-m , n)ans = min(ans , dp[i]);
	cout << sum - ans;
	return 0;
}
2024/8/5 18:44
加载中...