[DP思维] LSC分苹果 2018-小白月赛-7

链接：https://www.nowcoder.com/acm/contest/190/G
来源：牛客网

CLS 分苹果

orz 我好菜啊 dp数组大小 一直开的205 orz

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

CSL手上有n个苹果，第i个苹果的质量是wi，现在他想把这些苹果分给他的好朋友wavator和tokitsukaze。但是CSL为了不让他们打架，根据质量决定尽量地均分成两堆分给他们。现在CSL想知道到底给每个人分多少质量的苹果。 注意：苹果不能劈开来，并且如果不能正好均分，tokitsukaze小姐姐会拿到重的那一堆。
输入描述:
第一行输入一个整数n(2 ≤ n ≤ 100)，第二行n个整数，表示每个苹果的质量wi(1 ≤ wi ≤ 100)。
输出描述:
输出两个整数，分别表示wavator和tokitsukaze得到的苹果的质量。

示例1

输入

3
2 2 2

输出

2 4
官方题解：
G CSL 分苹果 做一个容量为 ⌊∑wi 2 ⌋ 的 01 背包即可得到 Wavator 分到苹果。 数据范围较小，各种正确的姿势都可以过。

既然是分一半最多 干脆01背包 到sum/2 最大就好了。orz

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;

const int maxn = 20000+5;

int w[maxn],dp[maxn];

int main(){
    int m,n;
    scanf("%d",&n);
    for (int i = 1;i <= n;i++){
        scanf("%d",&w[i]);
        m += w[i];
    }
    int t = m / 2;
    for (int i = 1;i <= n;i++){
        for (int j = t;j >= w[i];j--){   
            dp[j] = max(dp[j],dp[j - w[i]] + w[i]);
        }
    }
    printf("%d %d",dp[t],m - dp[t]);
    return 0; 
}