「NOIP模拟赛」某种数列问题
题目描述
众所周知，czy97有无数的妹子(阿掉！>_<)，而且他还有很多恶趣味的问题，继上次纠结于一排妹子的排法以后，今天他有非(chi)常(bao)认(cheng)真(zhe)去研究一个奇怪的问题。有一堆他的妹子站成一排，然后对于每个妹子有一个美丽度，当然美丽度越大越好，chenzeyu97妹子很多，但是质量上不容乐观，经常出现很多美丽度为负数的妹子(喜闻乐见)，czy97希望从一排妹子里找出3队连续的妹子，使她们的美丽度和最大。注意，一个妹子不能被编入多个队伍而且一定要拿出三队，不然czy会闲着没事做~。
简单滴说就是：
给定一个数列，从中找到3个无交集的连续子数列使其和最大。
输入
第一行一个数n，表示数列长度。
接下来有n行，每行一个数，第i行为第i个数。
输出
仅有一个数，表示最大和。
样例输入
10 -1 2 3 -4 0 1 -6 -1 1 -2
样例输出
7
提示
「样例说明」
第一队妹子取2，3。
第二队妹子取0，1。
第三队妹子取1。
「数据范围」
请大家放心，虽然chenzeyu97妹子无数，但是这次他叫来的个数n是有限的。=v=
对于30%的数据，妹子数不大于200。
对于60%的数据，妹子数不大于2000。
对于100%的数据，妹子数1000000。
而且，由于chenzeyu97没有CCR那样的影响力，所以他的妹子选完的最大美丽度和不超过maxlongint。(注:CCR随便选就爆long long，因为他是把妹狂魔=V=)。
题解
f[i][j][0/1]表示前i个取j段最后一个取或不取的最大值
或者可以参看「bzoj2288」「POJ Challenge」生日礼物
对于m>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 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #define inf 0x7fffffff using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();} return x*f; } int n,ans=-inf; int f[1000005][4][2];//0表示取最后一个，1表示不取 int a[1000005]; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=0;i<=n;i++) for(int j=0;j<=3;j++) f[i][j][0]=f[i][j][1]=-1000000000; f[1][0][0]=0;f[1][1][1]=a[1]; for(int i=2;i<=n;i++) for(int j=0;j<=3;j++) { f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]); if(j>0)f[i][j][1]=max(f[i-1][j-1][0]+a[i],f[i-1][j-1][1]+a[i]); f[i][j][1]=max(f[i][j][1],f[i-1][j][1]+a[i]); } for(int i=1;i<=n;i++) { ans=max(ans,f[i][3][0]); ans=max(ans,f[i][3][1]); } printf("%d",ans); //system("pause"); return 0; } |
Subscribe
计数器 9863349
OI 课件=>
OI 课件=>