转载请注明出处:http://tokitsukaze.live/

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6444


题意:
给出一个 n 个元素的环、可以任意选择起点、选完起点后、可以行走 m 步、每次前进 k 个单位、所走到的点将产生正或负贡献、问你一开始得准备多少才能使得初始资金加上在环上获取最大利益不少于给定的 s。


题解:
其实就是找走m步的途中获得的最大值mx。如果大于等于s,ans=0,否则ans=s-mx。
先暴力把每个环找出来。
对于每个环,我们考虑以下几个事情:
1.找到环的最优起点。
2.m步可以走很多次环。如果整个环的贡献为正,那么多的环的贡献就直接乘一下加进来,如果为负,可以只选择从最优起点开始走,或者甚至不走。

那么如何找到环的最优起点。其实这个问题就是找一个和最大的连续子序列且长度不超过len,len为单独考虑的步数。那么我们可以先做前缀和,数组为bit,问题就变成求bit[i]-bit[j-1]的最大值,且i-j+1<=len。然后控制窗口长度为len,进行滑窗,对于每个j-1,用单调队列来维护bit[i]的最大值,所以应该倒着for。
代码中维护的窗口长度是len+1,这样就变成求bit[i]-bit[j]的最大值,会好写一点。注意bit[0]=0,而且碰到bit[0]时默认入队,因为bit[1]可能是负的,所以这里要特判一下。

对于len的选取:

首先有一种情况是这样的:
5 100 12 1
-10 1 2 3 5
整个环的贡献是+1。
最优走法肯定是:
-10 {1 2 3 5}
如果我们选择2个整环+2步的话(len=2),最大值只能达到10。
但如果我们选择1个整环+7步的话(len=7),最大值可以达到12。
走法:
-10 {1 2 3 5,-10 1 2 3 5}

然后我的写法会出现第二种情况:
6 100 12 5
1 2 3 4 -5 6
整个环的贡献是+11。
如果我们选择2个整环+0步(len=0),最大值只能达到22。
但如果我们选择1个整环+6步(len=6),最大值可以达到27。
但是走法是这样的:
1 2 3 4 -5 {6 ,1 2 3 4 -5 6 ,1 2 3 4} -5 6
跨越了3个环。
所以对于我这种写法,这里的len要取12。要把环的数组复制3遍后再做前缀和。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
#ifdef tokitsukaze
freopen("TEST.txt","r",stdin);
#endif
go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=3.1415926;
const double eps=1e-6;
const int MAX=3e4+10;
const ll mod=1e9+7;
/********************************* head *********************************/
ll res[MAX],tmp[MAX],a[MAX],bit[MAX],dq[MAX];
int flag[MAX],tot;
ll n,s,m,k;
void gao(int pos)
{
int i,j,tag=pos+1,top=0,len;
ll cnt;
for(i=pos;flag[i]!=tag;i=(i+k)%n)
{
tmp[++top]=a[i];
flag[i]=tag;
}
for(i=1;i<=top;i++) tmp[i+top]=tmp[i+top*2]=tmp[i];
cnt=m/top;
len=m%top;
if(!len&&cnt)
{
len=top;
cnt--;
}
if(cnt)
{
cnt--;
len+=top;
}
top=top*3;
res[++tot]=0;
bit[0]=0;
for(i=1;i<=top;i++) bit[i]=bit[i-1]+tmp[i];
int l,r;
l=r=0;
for(i=j=top;i;i--)
{
while(~j&&i-j<=len)
{
while(r-l&&j&&bit[dq[r-1]]<bit[j]) r--;
dq[r++]=j--;
}
while(r-l&&dq[l]>i) l++;
res[tot]=max(res[tot],bit[dq[l]]-bit[dq[r-1]]);
}
if(bit[top/3]>=0) res[tot]+=bit[top/3]*cnt;
}
void go()
{
int t,cas=1,i;
read(t);
while(t--)
{
read(n,s,m,k);
for(i=0;i<n;i++) read(a[i]);
mem(flag,0);
tot=0;
for(i=0;i<n;i++)
{
if(flag[i]) continue;
gao(i);
}
ll ans=-LLINF;
for(i=1;i<=tot;i++) ans=max(ans,res[i]);
printf("Case #%d: %lld\n",cas++,max(0LL,s-ans));
}
}
/*
2
5 100 12 1
-10 1 2 3 5
6 100 12 5
1 2 3 4 -5 6

ans:
88
73
*/