2014
03-23

# 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

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了。

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;
}

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

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

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