问题 E: 积木

时间限制: 1 Sec 内存限制: 128 MB
提交: 36 解决: 14
[状态] [提交] [命题人:admin]
题目描述
乔治喜欢玩积木。目前他有N块积木，编号为1到N。所有积木的高度都是正整数，第i块积木高度是H[i]。乔治喜欢用积木堆起尽可能高的塔。他堆积木的过程中，只需要同时满足如下三个规则：
（1）积木必须堆放在同一个列中，一个搭在另一个上面。最终的塔的高度就是构成塔的所有积木的高度总和。
（2）塔中使用的积木的编号从底部到顶部必须是递增的。换句话说，每当乔治把积木x放在积木y的上面，必须要满足编号x大于编号y。
（3）乔治永远不会把高度是偶数的积木放置在高度是奇数的积木上面。

在满足上面的前提下，塔最高是多高？
输入
多组测试数据。
第一行，一个整数G，表示有G组测试数据。1<=G<=5。每组测试数据格式如下：
第1行，一个正整数N。2<=N<=50。
第2行，N个正整数，空格分开，第i个整数就是编号为i的积木的高度H[i]，1<=H[i]<=50。
输出
共G行，每行一个正整数。
样例输入 Copy
5
2
4 7
2
7 4
1
7
1
4
7
48 1 50 1 50 1 48
样例输出 Copy
11
7
7
4
196
提示
对于第5组测试数据的解释：
从底部往顶部，依次选择第1、第3、第5、第7块积木，这样塔的高度是：48+50+50+48=196。

本人由于不会dp直接做了。上代码吧。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int main() {
    int n,i,j,m,s,c,G,sum,t,k,t1,t2;
    scanf("%d",&G); 
    int a[100],b[100];
    while(G--){
        sum=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
        scanf("%d",&a[i]);
        if(a[i]%2==1)
        b[i]=1;
        else b[i]=0;
        }
        t=n;
        c=0;
        while(1){
            if(t==0)
            break;
            sum=0;
            for(i=1;i<=t;i++)
            if(b[i]==0)
            sum+=a[i];
            for(i=t;i<=n;i++)
            if(b[i]==1)
            sum+=a[i];
            c=max(c,sum);
            t--;
        }
    printf("%d\n",c);
    } 
    return 0;
}