PKU POJ 1014 Dividing

发表时间：2007年9月2日 18时7分17秒评论/阅读(2/11)

这道题的分类竟然在“简单”里面……
确实没有找到比较简单的方法

动态规划：

#include<stdio.h>
2

bool opt[60000];
3

int num=0;
4

int mid,max;
5

int stone[7];
6

int input()
7

{
8

scanf("%d%d%d%d%d%d",&stone[1],&stone[2],&stone[3],&stone[4],&stone[5],&stone[6]);
9

if(!stone[6]&&!stone[1]&&!stone[2]&&!stone[3]&&!stone[4]&&!stone[5]) {return 1;} //读到末行
10

num++;
11

printf("Collection #%d:\n",num);
12

mid=0;
13

for(int i=1;i<=6;i++) mid+=stone[i]*i;
14

if (mid % 2 ==1) //明显的剪枝
15

{
16

printf("Can't be divided.\n\n");
17

return 2;
18

}
19

else mid/=2; //我们的任务就是求opt
20

return 0;
21

}
22

void dp()
24

{
25

memset(opt,0,60000); //初始化，opt所有成员为false
26

opt[0]=true; //opt[0]显然是true
27

max=0; //当前最大值是0
28

for (int i=1;i<=6;i++)
30

{
31

if (stone[i]>0)
32

{
33

for(int j=max;j>=0;j--) // 从当前最大值开始往下算
34

if (opt[j]) //找到可行的j
35

{
36

if (opt[mid]) //判断是否已经求出结果
37

{
38

printf("Can be divided.\n\n");
39

return;
40

}
41

for (int k=1;k<=stone[i];k++) //在刚找到的可行j基础上加石头.
42

{
43

if (j+k*i>mid || opt[j+k*i]) break; //如果已经大于总价值的一半mid，或opt[j+k*i]已计算，跳出循环
44

opt[j+k*i]=true;
45

}
46

}
47

}
48

max=max+i*stone[i]; //更新当前最大值
49

if (max>mid) max=mid; //如果当前最大值超过了mid，对其赋值为mid
50

}
51

printf("Can't be divided.\n\n"); //如果从1到6循环完一遍后仍然没有算出opt[mid]，说明无解
52

}
53

int main()
55

{
56

while (1)
57

{
58

int t=input();
59

switch (t)
60

{
61

case 1 : return 0; //读到末行，结束
62

case 2 : continue; //读到明显的剪枝
63

default : dp();
64

}
65

}
66

return 0;
67

}

本题是找按价值均分大理石的方案是否存在，由于分配时不能破坏大理石，所以有个显而易见的剪枝：当所有的大理石的总价值为奇数时肯定不能被均分。
把问题转化一下即：由一个人能否从原大理石堆中取出总价值为原来一半的大理石
本题的主要算法是动态规划
数组opt代表状态：
设总价值为V,
当opt[k]==true时，说明，可以有一人获得价值k,另外一人获得价值V-k的大理石分配方案。反之若opt[k]=false 说明这种分配方案不存在
我们的任务就是计算出opt[v/2]是true还是false，即opt[mid]。
显然有opt[0]==true的方案存在，即一个人什么都不分，另外一个人拿走全部的大理石

设i（1<<6）为石头的价值，试想若opt[k]==true，而且在这堆总价值为k的石头中有一块石头的价值为i,那么opt[k-i]这种分配方案就是必然存在的了。反过来想，当opt[k]==true ，如果能再向k中增加一价值为i的大理石，则opt[k]==true必然成立
石头有两个属性，一个是价值另一个是数量，这里stone[i]代表价值为i的大理石的数量，我们根据其中一个属性：价值来划分阶段。
即for (int i=1;i<=6;i++)，opt[k]表示状态是否存在（这里的状态是指能否从原石头堆中分出价值为k的新石头堆）
在初始阶段是i=1,初始状态是opt[0],max代表目前满足opt[k]==true这一条件的k的最大值

for(int j=max;j>=0;j--)
//从当前最大值opt[开始]，根据前面提到的opt[j]==true成立则opt[j+i]==true亦成立的理论，在原有状态opt[j]==true已存在的条件下加入stone[i]阶段的石头,得到新的状态

PS :感谢重庆大学微软技术俱乐部的肖阳同学
原来这道题果然有更简单的方法
http://www.blogjava.net/zellux/archive/2007/07/30/133416.html

posted on 2007-09-14 02:11 流牛ζ木马阅读(4066) 评论(7) 编辑收藏引用

# re: PKU POJ 1014 Dividing 2008-11-05 23:56 zhao

如果输入是：
2 0 0 0 0 0
结果是：
Can't be divided.

? 回复更多评论

# re: PKU POJ 1014 Dividing 2009-03-23 22:17 allen

您好，我是刚接触ACM的菜鸟，拜读了您的解题思想，有个问题想请教一下，就是那个状态数组最大为60000个，这个数据有什么根据吗？回复更多评论

# re: PKU POJ 1014 Dividing 2009-04-17 16:53 黄河勇者

上面的提到状态数组最大为60000，是根据题意得出的，题意说最多有20000块石头，则一个人的最大价值为60000 回复更多评论

# re: PKU POJ 1014 Dividing 2009-04-17 20:02 黄河勇者

博主能不能将43行代码的opt[j+k*i]满足就跳出循环解释一下，小弟认为在当该条件满足时不一定要跳出循环（此处可能博主有误），因为opt[j+k*(i+1)]不一定计算出，所以循环有必要进行下去，如小弟理解有误，望博主指点。小弟的AC代码（算法思想按博主所写）：http://hi.baidu.com/黄河勇者回复更多评论

# re: PKU POJ 1014 Dividing 2009-08-29 15:01 lymfs

博主能不能将43行代码的opt[j+k*i]满足就跳出循环解释一下回复更多评论

# re: PKU POJ 1014 Dividing 2009-12-31 11:52 CRonaldo

@zhao
这是程序的一个bug.

根据你给出的"2 0 0 0 0 0",

尽管第44行中给opt[mid]赋值true,但程序却执行不到36行了.

可以做如下更正:
36                if (opt[mid])              //判断是否已经求出结果
37                {
38                    printf("Can be divided.\n\n");
39                    return;
40                }
41                for (int k=1;k<=stone[i];k++)         //在刚找到的可行j基础上加石头.
42                {
43                    if (j+k*i>mid || opt[j+k*i]) break; //如果已经大于总价值的一半mid，或opt[j+k*i]已计算，跳出循环
44                    opt[j+k*i]=true;
45                }

将上述的if语句和for循环对换.

@黄河勇者
@lymfs
opt[j+k*i]. 这里j初始化为max,并不断减小.
我们注意到,下一次循环中max实际上是由上一次的价值×数量(i*stone[i])累计而成;
而在累计过程中,opt相应位置不断赋值true.
刚开始j==max的时候,opt[j+k*i]显然不可能成立,

∵max是以前所有价值的和(排除max>mid的情况),

此时j+k*i显然大于max,即opt[j+k*i]从未被赋值过.
这就是说opt[j+k*i]==true成立的情况是在j不断减小的过程中发生的.
此时,分两种情况:
①j+k*i≥max.

除了opt[max],opt[j+k*i]是本次for(int j=max;j>=0;j--)循环中被赋值true,

即不存在opt[j+k*i]==true的情况.

②j+k*i<max.

可以将j+k*i看做小于max的j'.

显然j'是由max不断减小得到,j由j'不断减小得到,

opt[j]==true, opt[j']==true, j' - j == k*i.

j''==j+(k+1)*k, opt[j'']=?

还是无法用数学证明.继续研究...还请博主指点下.

回复更多评论

# re: PKU POJ 1014 Dividing 2010-08-08 01:38 444587868

Problem: 1014 User: 0809114213
Memory: 172K Time: 0MS
Language: C Result: Accepted

#include<stdio.h>
#include<string.h>
int shuzu[7];
char hehe[7][5000];
int f(int n,int sum)
{
int s=0,i=0,t=0;
if(!sum)
return 1;
if(!n)
if(sum)
return 0;
for(i=0;i<shuzu[n];i++)
if((s+=n)>sum)
break;
if(s>sum)
s-=n;
for(i=s/n;i>=0;i--)
for(t=1;t<=n-1;shuzu[0]+=shuzu[t]*t,t++)
if(shuzu[0]+(s/n-i)*n>=sum-i*n)
if(hehe[n-1][sum-i*n]!='0')
if(f(n-1,sum-i*n))
return 1;
else
hehe[n-1][sum-i*n]='0';
return 0;
}
void main(void)
{
int num=0,h=0,n=0;
while(1)
{ n=0;
memset(shuzu,0,sizeof(int)*7);
memset(hehe,'1',sizeof(char)*35000);
for(h=1;h<=6;n+=shuzu[h]*h,h++)
scanf("%d",shuzu+h);
if(!n)
break;
if(n%2)
printf("Collection #%d:\nCan't be divided.\n\n",++num);
else if(f(6,n/2))
printf("Collection #%d:\nCan be divided.\n\n",++num);
else
printf("Collection #%d:\nCan't be divided.\n\n",++num);
}
}

回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！



网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

2009年12月

日

一

二

三

四

五

六

统计

随笔 - 63
文章 - 0
评论 - 154
引用 - 0

公告

MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木马

常用链接

留言簿(6)

随笔档案

相册

撒旦

搜索

阅读排行榜

评论排行榜