NC15553 数学考试

数学考试

https://ac.nowcoder.com/acm/problem/15553

给定一个数组arr[ ](有正有负),选择两段子数组(子数组长度等于K)

求和最大的两段子数组,打印和

  • 先求前缀和

状态表示:

<mtext>          </mtext> l e f [ i ] ~~~~~~~~lef[i]         lef[i]表示 i i i的左边的长度为K的子数组最大和(包括 i i i)

<mtext>          </mtext> r i g [ i ] ~~~~~~~~rig[i]         rig[i]表示 i i i的右边的长度为K的子数组最大和(包括 i i i)

转移方程:

<mtext>          </mtext> l e f [ i ] = m a x ( l e f [ i 1 ] , s u m [ i ] s u m [ i K ] ) ~~~~~~~~lef[i]=max(lef[i-1],sum[i]-sum[i-K])         lef[i]=max(lef[i1],sum[i]sum[iK])

<mtext>          </mtext> r i g [ i ] = m a x ( r i g [ i + 1 ] , r i g [ i + K 1 ] s u m [ i 1 ] ) ~~~~~~~~rig[i]=max(rig[i+1], rig[i+K-1]-sum[i-1])         rig[i]=max(rig[i+1],rig[i+K1]sum[i1])

<mtext>          </mtext> a n s = m a x ( a n s , l e f [ i ] + r i g [ i + 1 ] ) ~~~~~~~~ans=max(ans,lef[i]+rig[i+1])         ans=max(ans,lef[i]+rig[i+1])
初始状态
<mtext>          </mtext> l e f [ <mtext>   </mtext> ] r i g [ <mtext>   </mtext> ] , ~~~~~~~~lef[~]和rig[~]应该初始化为最小,因为有负数         lef[ ]rig[ ],
<mtext>          </mtext> m e m s e t ( l e f , 0 x 7 f , s i z e o f ( l e f ) ) ~~~~~~~~memset(lef,-0x7f,sizeof(lef))         memset(lef,0x7f,sizeof(lef))

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN ((int)2e5+7)
#define ll long long 
#define int long long 
#define INF (0x7f7f7f7f)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)
void err() { cout << "\033[39;0m" << endl; }
#endif

template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

//从一个数组里选两段长度为K的子数组a1[],a2[],要求sum_a1+sum_a2最大
int n, m, Q, K, a[MAXN], sum[MAXN];
ll lef[MAXN]; //表示位置i左边长度为K的子数组(包括i)的最大和
ll rig[MAXN]; //表示位置i右边长度为K的子数组(包括i)的最大和

signed main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	scanf("%lld ", &Q);
	while(Q--) {
		scanf("%lld %lld ", &n, &K);
		
		memset(sum, 0, sizeof(sum));
		memset(lef, -0x7f, sizeof(lef));
		memset(rig, -0x7f, sizeof(rig));
	
		for(int i=1; i<=n; i++) 
			scanf("%lld ", a+i), sum[i]=sum[i-1]+a[i];

		for(int i=K; i<=n-K; i++) 
			lef[i] = max(lef[i-1], (sum[i]-sum[i-K]));

		for(int i=n-K+1; i>=K+1; i--) 
			rig[i] = max(rig[i+1], (sum[i+K-1]-sum[i-1]));

		//forarr(lef, 1, n, "lef");
		//forarr(rig, 1, n, "rig");
		int ans = -1e18;
		for(int i=K; i<=n-K; i++) 
			ans = max(ans, lef[i]+rig[i+1]);
		printf("%lld \n", ans);
	}




#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}


全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务