Dividing
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 54064 | Accepted: 13818 |
Description
Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value. Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.
Input
Each line in the input file describes one collection of marbles to be divided. The lines contain six non-negative integers n1 , . . . , n6 , where ni is the number of marbles of value i. So, the example from above would be described by the input-line "1 0 1 2 0 0". The maximum total number of marbles will be 20000.
The last line of the input file will be "0 0 0 0 0 0"; do not process this line.
The last line of the input file will be "0 0 0 0 0 0"; do not process this line.
Output
For each collection, output "Collection #k:", where k is the number of the test case, and then either "Can be divided." or "Can't be divided.".
Output a blank line after each test case.
Output a blank line after each test case.
Sample Input
1 0 1 2 0 0 1 0 0 0 1 1 0 0 0 0 0 0
Sample Output
Collection #1: Can't be divided. Collection #2: Can be divided.
题意:
有6种大理石,给出每种大理石的数量和价值,用num[ i ](不超过20000)表示,i 代表价值,num[ i ]代表数量。判断是否能平均分成两堆价值一样的大理石。
思路:
多重背包。
AC1:
#include<stdio.h> #include<string.h> #define max 1000000 int dp[500000],val[50000]; int main() { int num[11],time=1; while(scanf("%d%d%d%d%d%d",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6])!=EOF) { int sum=0,half,k=0; dp[0]=0; for(int i=1;i<500000;i++) dp[i]=-max; for(int i=1;i<=6;i++) sum+=num[i]*i; if(!sum) break; printf("Collection #%d:\n",time++); if(sum%2) printf("Can't be divided.\n\n"); else { half=sum/2; for(int i=1;i<=6;i++) { for(int j=1;j<=num[i];j++) val[k++]=j*i,num[i]-=j; if(num[i]>0) val[k++]=num[i]*i; } for(int i=0;i<k;i++) for(int j=half;j>=val[i];j--) if(dp[j-val[i]]+val[i]>dp[j]) dp[j]=dp[j-val[i]]+val[i]; if(dp[half]<0) printf("Can't be divided.\n\n"); else printf("Can be divided.\n\n"); } } return 0; }
AC2比AC1要更省时间。
AC2:
#include<stdio.h> #include<string.h> #define max 1000000 int sum,half; int dp[200000]; void zeroonepack(int value) { for(int i=half;i>=value;i--) if(dp[i]<dp[i-value]+value) dp[i]=dp[i-value]+value; } void completepack(int value) { for(int i=value;i<=half;i++) if(dp[i]<dp[i-value]+value) dp[i]=dp[i-value]+value; } void multipack(int value,int number) { int k=1; if(value*number>half) completepack(value); while(k<number) { zeroonepack(k*value); number-=k; k+=k; } zeroonepack(number*value); } int main() { int num[10]; int time=1; while(scanf("%d%d%d%d%d%d",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6])!=EOF) { sum=0; dp[0]=0; for(int i=1;i<=6;i++) sum+=num[i]*i; if(!sum) break; printf("Collection #%d:\n",time++); if(sum%2) printf("Can't be divided.\n\n"); //如果总价值为单数的时候,无论怎么分都不可能分成平均的两份 else { for(int i=1;i<200000;i++) dp[i]=-max; half=sum/2; for(int i=1;i<=6;i++) //是每一个数都要进行一次01背包 multipack(i,num[i]); if(dp[half]<0) printf("Can't be divided.\n\n"); //输出格式注意 else printf("Can be divided.\n\n"); } } return 0; }
总结:
1.输出格式没看清;
2.总数为单数的情况没考虑仔细;
3.注意数组开的大小。
相关推荐
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
Simple Dividing Number Game using JavaScript with Free Source Code
Pku acm 第1014题 Dividing c代码,有详细的注释,动态规划
Matlab Tutorial - 39 - Multiplying and Dividing Matrices Element-by-Element
Attachment B Models for Dividing Fractions 附件 B 分数除法模型.doc
研究关于将一个矩形分割为多个矩形的论文,来自路易斯安那州立大学数学系,亦可从作者的个人主页上下载: www.math.lsu.edu/~verrill/research/rectangles.pdf
杭电OJ(1000-1099) AC 代码
a high linearized photonic mixer based on unsymmetrical power dividing for ROF system
基于空分复用弹性光网络的路由与资源分配算法,王晨戈,尹珊,随着互联网技术的发展与各种新应用的出现,需要的网络容量快速增长。而传统的单模光纤的传输容量已经逼近极限,基于空分复用(Spa
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
$ git clone https://github.com/Alladin9393/Search-For-Dividing-Circle.git && cd Search-For-Dividing-Circle $ virtualenv venv -p python3 && source venv/bin/activate $ pip3 install -r requirements.txt ...
Dividing-by-the-number-11:查找要添加到一个数字的数字,以便将输入的数字除以11
html事件改变矩形大小源码 区域1 <div id="dividing-line1"> 区域2 <div id="dividing-line2"> 区域3 </template>
The.Definitive.Guide.to.SWT.and.JFace.eBook-LiB [SWT/JFace开发指南]
The impact factor of a journal is calculated by dividing the number of current year citations to the source items published in that journal during the previous two years. It is an independent measure...
QGridLayout lays out widgets in cells by dividing the available space into rows and columns. QFormLayout, on the other hand, sets its children in a two-column form with labels in the left column and ...
This guide to thesis writing gives some simple and practical advice on the problems of getting started, getting organized, dividing the huge task into less formidable pieces and working on those ...
YAFFS is a log-structured ...is determined by dividing the file position by the chunk size. Each chunk has a number of valid bytes, which equals the page size for all except the last chunk in a file.
GridLineParams: TDBVertGridLineParamsEh - Color settings of the dividing lines in vertical grid. DataColParams: TDBVertGridDataColParamsEh - The setting of the column with data. LabelColParams: ...
A description of general techniques for solving linear partial differential equations by dividing space into regions to which the equations are independently applied and then assembling a global ...