• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

某种数列问题(jx.cpp/c/pas)1000MS256MB

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

众所周知,chenzeyu97有无数的妹子(阿掉!>_<),而且他还有很多恶趣味的问题,继上次纠结于一排妹子的排法以后,今天他有非(chi)常(bao)认(cheng)真(zhe)去研究一个奇怪的问题。有一堆他的妹子站成一排,然后对于每个妹子有一个美丽度,当然美丽度越大越好,chenzeyu97妹子很多,但是质量上不容乐观,经常出现很多美丽度为负数的妹子(喜闻乐见),chenzeyu97希望从一排妹子里找出3队连续的妹子,使她们的美丽度和最大。注意,一个妹子不能被编入多个队伍而且一定要拿出三队,不然czy会闲着没事做~。

简单滴说就是:

给定一个数列,从中找到3个无交集的连续子数列使其和最大。

【输入文件】

第一行一个数n,表示数列长度。

接下来有n行,每行一个数,第i行为第i个数。

【输出文件】

仅有一个数,表示最大和。

【样例输入】 jx.in

10

-1   2   3   -4   0   1   -6   -1   1   -2

【样例输出】 jx.out

7

【样例说明】

第一队妹子取2,3。

第二队妹子取0,1。

第三队妹子取1。

【数据范围】

请大家放心,虽然chenzeyu97妹子无数,但是这次他叫来的个数n是有限的。=v=

对于30%的数据,妹子数不大于200。

对于60%的数据,妹子数不大于2000。

对于100%的数据,妹子数1000000。

而且,由于chenzeyu97没有CCR那样的影响力,所以他的妹子选完的最大美丽度和不超过maxlongint。(注:CCR随便选就爆long long,因为他是把妹狂魔=V=)。

這道題顯然是DP,而且很容易看出是三維的。

f[i][0,1,2,3][0,1],i是代表選取的第幾個妹子,0,1,2,3表示還可以選機隊妹子,0,1表示當前的妹子選不選。

傻傻的不會推DP方程,於是,就算當前的妹子加上前一個序號的某個f等於什麼。

s[i]+f[i-1][3][0]=f[i][2][1];
s[i]+f[i-1][2][0]=f[i][1][1];
s[i]+f[i-1][1][0]=f[i][0][1];
s[i]+f[i-1][2][1]=f[i][2][1];
s[i]+f[i-1][1][1]=f[i][1][1];
s[i]+f[i-1][0][1]=f[i][0][1];

然后,倒過來,順便加上f[?][?][0]=?.(顯然,f[?][3][0]只能等於0,所以我就換成0了,又因為f[?][3][1]不存在,於是順便給第二維壓縮了一下。)

f[i][2][1]=max(s[i],s[i]+f[i-1][2][1]);
f[i][2][0]=max(f[i-1][2][0],f[i-1][2][1]);
f[i][1][1]=max(s[i]+f[i-1][2][0],s[i]+f[i-1][1][1]);
f[i][1][0]=max(f[i-1][1][0],f[i-1][1][1]);
f[i][0][1]=max(s[i]+f[i-1][1][0],s[i]+f[i-1][0][1]);
f[i][0][0]=max(f[i-1][0][0],f[i-1][0][1]);
因為某些原因,還要把“lld”和“I64d”重定義為LL(這個是什麼不重要)。
#ifdef unix
#define LL "%lld"
#else
#define LL "%I64d"
#endif
為了節約空間,我順便把第一維壓縮了,從n到2,代碼裡的b,c,%2就是關鍵。

代碼實現:

 1 #include<cstdio>
 2 #include<iostream>
 3 #ifdef unix
 4 #define LL "%lld"
 5 #else
 6 #define LL "%I64d"
 7 #endif
 8 using namespace std;
 9 long long n,a,b,c,f[2][4][2];
10 int main(){
11     freopen("jx.in","r",stdin);
12     freopen("jx.out","w",stdout);
13     scanf(LL,&n);
14     for(int i=1;i<=n;i++){
15         scanf(LL,&a);
16         b=(i-1)%2;c=i%2;
17         f[c][2][1]=max(a,a+f[b][2][1]);
18         f[c][2][0]=max(f[b][2][0],f[b][2][1]);
19         f[c][1][1]=max(a+f[b][2][0],a+f[b][1][1]);
20         f[c][1][0]=max(f[b][1][0],f[b][1][1]);
21         f[c][0][1]=max(a+f[b][1][0],a+f[b][0][1]);
22         f[c][0][0]=max(f[b][0][0],f[b][0][1]);
23     }
24     printf(LL"\n",max(f[n%2][0][0],f[n%2][0][1]));
25     return 0;
26 }

吐槽一下,我1~n cin流讀入只得了60分(那四十分T了)。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C++输出一个菱形发布时间:2022-07-13
下一篇:
C#设计模式之4:装饰者模式发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap