//poj2576

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,v,wei,f[105];
int a[22505][55];
int b[23505][55];

void into()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&f[i]);
		wei+=f[i];
	}
	v=wei/2;m=n/2;
	if(n%2!=0)m++;
}

void js()
{
	for(int i=1;i<=n;i++)
		for(int j=v;j>=f[i];j--)
			for(int k=1;k<=m;k++)
			{
				if(a[j-f[i]][k-1]+1>a[j][k])
				{
					a[j][k]=a[j-f[i]][k-1]+1;
					b[j][k]=b[j-f[i]][k-1]+f[i];
				}
				else if((a[j-f[i]][k-1]+1==a[j][k])&&(b[j-f[i]][k-1]+f[i]>b[j][k]))b[j][k]=b[j-f[i]][k-1]+f[i];
			}
	if(wei-b[v][m]>b[v][m])printf("%d %d\n",b[v][m],wei-b[v][m]);
	else printf("%d %d\n",wei-b[v][m],b[v][m]);
}

int main()
{
	into();
	js();
	return 0;
}

• Re:DP (938) lzxzy 2018-08-01 15:00:55
• 厉害了 (2) ACAccepted 2018-08-20 16:06:50
  • O__O"… (6) 951753852456 2018-08-21 11:11:25
    • 咕~~(╯﹏╰)b (9) hntby 2018-08-21 11:12:42
      • ( ⊙ _ ⊙ )一般吧 (12) cdtby 2018-08-21 11:14:22
        • 还有测评点吗？ (0) lztby 2018-08-21 11:16:03
• Re:DP (938) ACAccepted 2019-02-23 20:55:46