游客 注册 | 登录
中文 | En

3028 - 小俞同学的游戏

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

一天，小俞同学突然之间就很没意思，于是她找来了你来玩游戏。她拿来了一堆卡片，把上面都写上了数字，并且把它们分成n摞。游戏的规则是这样的，你俩只可以从一摞牌的上面取一张或者是下面取一张（她想取上面的，于是你只好取下面的了）。

轮流取牌，你们也可以取不同的一摞的牌，只要遵守上面的规则即可。由于规则是她想出来的，所以，也是她先取牌。你俩都非常的聪明，都能用最优的策略来玩游戏，现在由你来算出最后的得分。

题目输入

第一行一个整数n（1<=n<=100).

第二行的第一个整数m代表每一摞有多少张牌（1<=m<=100)，接下来m个整数Ci，代表第i张上面的分数(1<=Ci<=1000)

题目输出

一行两个整数p和q，代表小俞同学的得分和你的得分。

输入/输出样例

输入格式

2
1 100
2 1 10
1
9 2 8 6 5 9 4 7 1 3
3
3 1 3 2
3 5 4 6
2 8 7
3
3 1000 1000 1000
6 1000 1000 1000 1000 1000 1000
5 1000 1000 1000 1000 1000

输出格式

101 10
30 15
18 18
7000 7000

C++解答

#include<iostream>  
#include<cmath>  
#include<cstring>  
#include<cstdio>  
#include<algorithm>  
using namespace std;  
  
int n;  
int s[123];  
int a[123];  
int last[123];  
  
bool cmp(int a,int b){  
    return a>b;  
}  
  
int main(){  
    while(~scanf("%d",&n)){  
        int alice=0,bob=0;  
        int half,cnt=0;  
        int get = 0;  
        for(int i=0;i<n;i++){  
            scanf("%d",&s[i]);  
            for(int j=0;j<s[i];j++){  
                scanf("%d",&a[j]);  
            }  
            half = s[i]/2;  
            //一人一半  
            if(s[i]%2==0){  
                for(int j=0;j<half;j++){  
                    alice+=a[j];  
                    get++;  
                }  
                for(int j=half;j<s[i];j++){  
                    bob+=a[j];  
                    get++;  
                }  
            }  
            //剩了一个  
            else{  
                for(int j=0;j<half;j++){  
                    alice+=a[j];  
                    get++;  
                }  
                last[cnt++] = a[half];  
                for(int j=half+1;j<s[i];j++){  
                    bob+=a[j];  
                    get++;  
                }  
            }  
        }  
        if(cnt!=0){  
            sort(last,last+cnt,cmp);  
            //alice first  
            if(get%2==0){  
                for(int i=0;i<cnt;i++){  
                    if(i%2==0){  
                        alice+=last[i];  
                    }  
                    else{  
                        bob+=last[i];  
                    }  
                }  
            }  
            //bob first  
            else{  
                for(int i=0;i<cnt;i++){  
                    if(i%2==1){  
                        alice+=last[i];  
                    }  
                    else{  
                        bob+=last[i];  
                    }  
                }  
            }  
        }  
        printf("%d %d\n",alice,bob);  
    }  
    return 0;  
}
请先登陆