客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
众所周知，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了)。 |
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期
今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知
今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道
今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要
我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多
今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不
电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很
我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法
今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win
今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎
请发表评论