小埋的最大连续子序列 求调

问题讨论区 普及段
1

题面：
image

#include<bits/stdc++.h>

using namespace std;
int t, n;
int a[100005], dp[100005];//以a[i]为结尾的最大连续子序列之和
bool check(int x){
    if (x % 2 == 0) return 1;
    if (x % 2 == 1) return 0;
}
int main(){
    cin >> t;
    while (t --){
        cin >> n;
        for (int i = 1;i <= n;++ i){
            cin >> a[i];
            dp[i] = 1;
        }
        for (int i = 1;i <= n;++ i)
            for (int j = 1; j <= i - 1;++ j){
                if (check (a[i]) != check (a[j]))
                    dp[i] = max (dp[i] + a[i], dp[j]);
            }
        int maxn = -1e8;
        for (int i = 1;i <= n;++ i)
            maxn = max (maxn, dp[i]);
        cout << maxn << endl;
    }
    return 0;
}
2

是什么错误？？几分？？ @蓝天鸿

3

有阳历么

4

为什么等于1
@蓝天鸿

建议你check时要判断复数的情况，因为负数取模有问题，要先转成正数（abs)

5

负数取模会有问题，可以先对x取个abs

6

@蓝天鸿 @蓝天鸿 @

7

dp[i] = a[i]

8

image
应该是这里的问题

9

稍等，你为啥有两层循环？

10

是dp[i]=max(dp[i],dp[j]+a[i]);

11

这题的子序列是连续的，你的代码不一定是连续的

12

子序列不连续！！！字串是连续的

13

但是题目说是连续子序列，所以要当成字串

14

所以你错了，单循环即可，用前一个元素进行转移

15

所以应该只有一层循环

16

是这样的

17

你应该有WA和TLE

18

@蓝天鸿 @蓝天鸿

19

你的a[i]应该加在dp[i-1]上

20 
for(int i = 2;i <= n;++ i){
			if(check (a[i - 1], a[i]))
				cnt = max (a[i], cnt + a[i]);
			else
				cnt = a[i];
			ans = max (ans, cnt);
		}

应该是这样