列表

详情

NC24614. [USACO 2011 Jan S]Dividing the Gold

描述

Bessie and Canmuu found a sack of N (1 <= N <= 250) gold coins that they wish to divide as evenly as possible. Coin i has value V _i (1 <= V_i <= 2,000). The cows would like to split the pile as evenly as they can, but that is not always possible. What is the smallest difference between the values of the two piles?
In addition, the Bessie and Canmuu have found that there might be multiple ways to split the piles with that minimum difference. They would also like to know the number of ways to split the coins as fairly as possible. If it isn't possible to split the piles evenly, Bessie will get the higher-valued pile.
By way of example, consider a sack of five coins of values: 2, 1, 8, 4, and 16. Bessie and Canmuu split the coins into two piles, one pile with one coin worth 16, and the other pile with the remaining coins worth 1+2+4+8=15. Therefore the difference is 16-15 = 1. This is the only way for them to split the coins this way, so the number of ways to split it evenly is just 1.
Note that same-valued coins can be switched among the piles to increase the number of ways to perform an optimal split. Thus, the set of coins {1, 1, 1, 1} has six different ways to split into two optimal partitions, each with two coins.

输入描述

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: V_i

输出描述

* Line 1: A single integer that is the smallest difference of two partitions.
* Line 2: A single integer that is the number of ways to split the coins with the minimum difference printed in line 1. Since this number can get quite large, print the remainder when divided by 1,000,000.

示例1

输入: 

5 
2 
1 
8 
4 
16

输出: 

1
1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 261ms, 内存消耗: 2680K, 提交时间: 2020-03-02 17:08:03 

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
const int p=1000000;
int n,x,f[600000],sum;
bool g[600000];
int main(){
	scanf("%d",&n);
	f[0]=1;g[0]=1;
	fo(i,1,n){
		scanf("%d",&x);
		sum+=x;
		fd(j,sum,x){
			g[j]|=g[j-x];
			f[j]+=f[j-x];
			if (f[j]>=p) f[j]-=p;
		}
	}
	fo(i,(sum+1)/2,sum) if (g[i]){
		printf("%d\n%d\n",i-(sum-i),f[i]);
		return 0;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 330ms, 内存消耗: 5472K, 提交时间: 2020-03-29 16:38:24 

#include<bits/stdc++.h>
using namespace std;
int n,a[350],pig,s,f[500005];
long long dp[500005];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i],s+=a[i];
	pig=s;
	s/=2;
	for(int i=1;i<=n;i++)
	for(int j=s;j>=a[i];j--)
	f[j]=max(f[j],f[j-a[i]]+a[i]);
	cout<<pig-2*f[s]<<endl;
	dp[0]=1;
	for(int i=1;i<=n;i++)
	for(int j=pig;j>=a[i];j--)
	dp[j]=(dp[j]+dp[j-a[i]])%1000000;
	cout<<dp[f[s]]<<endl;
	return 0;
}

上一题

© 2024 nowcoder.com