洛谷 P3040 [USACO12JAN]贝尔分享Bale Share
P3040 [USACO12JAN]贝尔分享Bale Share
题目描述
Farmer John has just received a new shipment of N (1 <= N <= 20) bales of hay, where bale i has size S_i (1 <= S_i <= 100). He wants to divide the bales between his three barns as fairly as possible.
After some careful thought, FJ decides that a "fair" division of the hay bales should make the largest share as small as possible. That is, if B_1, B_2, and B_3 are the total sizes of all the bales placed in barns 1, 2, and 3, respectively (where B_1 >= B_2 >= B_3), then FJ wants to make B_1 as small as possible.
For example, if there are 8 bales in these sizes:
2 4 5 8 9 14 15 20
A fair solution is
Barn 1: 2 9 15 B_1 = 26
Barn 2: 4 8 14 B_2 = 26
Barn 3: 5 20 B_3 = 25
Please help FJ determine the value of B_1 for a fair division of the hay bales.
FJ有N (1 <= N <= 20)包干草,干草i的重量是 S_i (1 <= S_i <= 100),他想尽可能平均地将干草分给3个农场。
他希望分配后的干草重量最大值尽可能地小,比如, B_1,B_2和 B_3是分配后的三个值,假设B_1 >= B_2 >= B_3,则他希望B_1的值尽可能地小。
例如:8包干草的重量分别是:2 4 5 8 9 14 15 20,一种满足要求的分配方案是
农场 1: 2 9 15 B_1 = 26
农场 2: 4 8 14 B_2 = 26
农场 3: 5 20 B_3 = 25
请帮助FJ计算B_1的值。
输入输出格式
输入格式:
Line 1: The number of bales, N.
- Lines 2..1+N: Line i+1 contains S_i, the size of the ith bale.
输出格式:
- Line 1: Please output the value of B_1 in a fair division of the hay bales.
输入输出样例
8
14
2
5
15
8
9
20
4
26
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 30
using namespace std;
int n;
int A,B,C;
int ans=0x7f7f7f7fl;
int sum[MAXN];
void dfs(int now){
if(max(A,max(B,C))>ans) return ;
if(now==n+){
ans=max(A,max(C,B));
return;
}
A+=sum[now];dfs(now+);A-=sum[now];
B+=sum[now];dfs(now+);B-=sum[now];
C+=sum[now];dfs(now+);C-=sum[now];
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&sum[i]);
dfs();
cout<<ans;
}
60分的dfs
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 30
using namespace std;
int n;
int A,B,C;
int ans=0x7f7f7f7fl;
int sum[MAXN];
void dfs(int now){
if(now==n+){
ans=max(A,max(C,B));
return;
}
A+=sum[now];if(A<ans) dfs(now+);A-=sum[now];
B+=sum[now];if(B<ans) dfs(now+);B-=sum[now];
C+=sum[now];if(C<ans) dfs(now+);C-=sum[now];
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&sum[i]);
dfs();
cout<<ans;
}
AC的dfs
正解思路:动态规划。
f[i][j][k]表示到第i堆干草为止,第一个农场分到j的干草,第二个农场分到k的干草。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 10010
using namespace std;
int n;
int dp[][20][20];
int num[MAXN],sum[MAXN];
int dfs(int now,int x,int y){
int z=sum[now-]-x-y;
if(now==n+) return max(x,max(y,z));
if(dp[now][x][y]) return dp[now][x][y];
dp[now][x][y]=min(dfs(now+,x+num[now],y),min(dfs(now+,x,y+num[now]),dfs(now+,x,y)));
return dp[now][x][y];
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&num[i]);
for(int i=;i<=n;i++) sum[i]=sum[i-]+num[i];
dfs(,,);
cout<<dp[][][];
}
最新文章
- 使用 ODBC .NET 提供程序和 Visual C# .NET 执行 SQL 参数化存储过程
- 深入理解js——一切都是对象
- hdu 4711 动态规划
- 让JAVA代码跑得更快
- 使用Xmanager工具连接Linux服务器
- A + B Problem II---hdu1002
- 转:一道笔试题-将int型数组强制转换为char*,再求strlen,涉及大小端
- JavaScript引用类型之Object类
- 【本&#183;伍德Lua专栏】补充的基础09:使用table.concat将一个大的字符串
- maven构建这么慢,怎么改变?
- iOS开发之UINavigationController
- C语言代码训练(一)
- SpringSecurity如何退出登录
- Docker入门 - 005 Docker 容器连接
- git心得
- spring事务中出现oracle游标溢出的解决方案
- 微信小程序开发之获取用户手机号码——使用简单php接口demo进行加密数据解密
- Java8 Collectors.toMap的坑
- js全选反选
- 一个用css写出来的下拉菜单
热门文章
- CCEditBox/CCEditBoxImplAndroid
- Precision and recall From Wiki
- gem5中event queue执行原理机制具体分析
- H5学习_番外篇_PHP数据库操作
- jsp出现错误can not find the tag directory /web-inf/tags
- Flume框架基础
- iOS开发下对MVVM的理解
- PostgreSQL Replication之第七章 理解Linux高可用(2)
- POJ 3630 Phone List(字典树)
- python etree.HTML