首页 > ACM题库 > HDU-杭电 > HDU 3415-Max Sum of Max-K-sub-sequence-分治-[解题报告]HOJ
2014
03-23

HDU 3415-Max Sum of Max-K-sub-sequence-分治-[解题报告]HOJ

Max Sum of Max-K-sub-sequence

问题描述 :

Given a circle sequence A[1],A[2],A[3]……A[n]. Circle sequence means the left neighbour of A[1] is A[n] , and the right neighbour of A[n] is A[1].
Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K.

输入:

The first line of the input contains an integer T(1<=T<=100) which means the number of test cases.
Then T lines follow, each line starts with two integers N , K(1<=N<=100000 , 1<=K<=N), then N integers followed(all the integers are between -1000 and 1000).

输出:

The first line of the input contains an integer T(1<=T<=100) which means the number of test cases.
Then T lines follow, each line starts with two integers N , K(1<=N<=100000 , 1<=K<=N), then N integers followed(all the integers are between -1000 and 1000).

样例输入:

4
6 3
6 -1 2 -6 5 -5
6 4
6 -1 2 -6 5 -5
6 3
-1 2 -6 5 -5 6
6 6
-1 -1 -1 -1 -1 -1

样例输出:

7 1 3
7 1 3
7 6 2
-1 1 1

题意:给出一个有N个数字(-1000..1000,N<=10^5)的环状序列,让你求一个和最大的连续子序列。这个连续子序列的长度小于等于K。这题是我们比赛题,当时不会写,不会单调队列,现在会了,果断把它给A了,但还是贡献了很多个wa,tle,re,先前wa就一直改,本来对的改的乱七八糟,其实就是数组开小了,蛋疼了一个晚上,后面果断删掉重写,re后就A了,这题其实很好想,可以说一般人都知道怎么做,首先我先讲讲dp中的最大子段和,有几种解法,直接暴力o(n^3),部分和o(n^2),分治o(nlg(n)),dp
o(n);如果说有人硬要说这题是dp,我没办法,还说了状态的转移可以证明,我的第一直观这种一段一段的和而且是要求位置的题目,一般都是用部分和求解的,虽然我很菜,也知道dp一般是对全局求最优,求子问题还不如用分治(不过还要找位置就麻烦了),这题就是一个部分和的问题,sum[i]-sum[i-j]=sum(i~j);这东西小学生都知道,不需要我去证明了,问题就是求max(sum[i-j](i-j<=k)), 显然是sum[i]-sum[j]最大,i-k<j<i,就是求min 
sum[j];这就是一个单调队列的问题了,只要枚举终点的位置就ok了。

单调对列的stl写法很简单,别人写的。看到就贴过来了(插入的下标)

deque<int> q;
        q.clear();
  while(!q.empty() && sum[j-1]<sum[q.back()])
        q.pop_back();
  while(!q.empty() && q.front()<(j-K))
        q.pop_front();
        q.push_back(j-1);

我的用的是手写版的,还好吧

#include<stdio.h>
struct queuey
{
	int key,flag;
}q[200005];
int r,f;
int insert(int flag,int key)
{
	while(r>f&&key<q[r].key)
		r--;
	q[++r].flag=flag;
	q[r].key=key;
	return 1;
}
void init()
{
	f=r=0;
}
int a[100005],sum[200005];
int main()
{
	int n,m,c,ans,x,y,i;
	scanf("%d",&c);
	while(c--)
	{
		scanf("%d%d",&n,&m);
		sum[0]=0;init();
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum[i]=sum[i-1]+a[i];
		}
		for(i=n+1;i<n+m;i++)
			sum[i]=sum[i-1]+a[i-n];
		ans=-0x3fffffff;
		for(i=1;i<n+m;i++)
		{
			while(q[f+1].flag<i-m&&f<r)
					f++;
				insert(i-1,sum[i-1]);				
				if(sum[i]-q[f+1].key>ans)
				{
					ans=sum[i]-q[f+1].key;
					x=q[f+1].flag+1;
				    y=i;
				}
		}
		printf("%d %d %d\n",ans,x,y<=n?y:y%n);
	}
	return 0;
}


参考:http://blog.csdn.net/xymscau/article/details/6677427


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。