久久久久成人网,亚洲一线二线三线久久久,久久国产精品网站

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 流牛ζ木馬閱讀(4087) 評論(7) 編輯收藏引用

博主能不能將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 管理

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

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

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

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

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

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

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

PKU POJ 1014 Dividing

PKU POJ 1014 Dividing

評論

導航

統計

公告

常用鏈接

留言簿(6)

隨筆檔案

相冊

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜