青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

PKU POJ 1014 Dividing

PKU POJ 1014 Dividing

發表時間:2007年9月2日 18時7分17秒        評論/閱讀(2/11)
這道題的分類竟然在“簡單”里面…… 
確實沒有找到比較簡單的方法 

動態規劃: 

 1#include<stdio.h> 
 2bool opt[60000]; 
 3int num=0
 4int mid,max; 
 5int stone[7]; 
 6int 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
23void dp() 
24
25    memset(opt,0,60000);          //初始化,opt所有成員為false 
26    opt[0]=true;                        //opt[0]顯然是true 
27    max=0;                             //當前最大值是0 
28
29    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
54int 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 流牛ζ木馬 閱讀(4094) 評論(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);
}
}


  回復  更多評論   


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


<2007年9月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

導航

統計

公告

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

常用鏈接

留言簿(6)

隨筆檔案

相冊

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲黄色在线观看| 日韩亚洲国产欧美| 亚洲一区二区少妇| 国产精品麻豆欧美日韩ww| 亚洲一区二区三区久久| 亚洲最新在线视频| 国产精品一区二区三区观看| 欧美一二三区在线观看| 亚洲综合99| 精品1区2区| 91久久综合亚洲鲁鲁五月天| 欧美日韩一区成人| 欧美一区二区三区在线看| 午夜视频在线观看一区| 亚洲承认在线| 亚洲人成免费| 国产女主播一区二区三区| 久久久视频精品| 欧美国产亚洲另类动漫| 欧美一区二区三区视频在线 | 亚洲曰本av电影| 国产一区视频网站| 欧美高清视频在线| 国产精品久久久久久av下载红粉 | 午夜精品美女久久久久av福利| 亚洲一区二区在线免费观看| 国产一区二区三区黄| 欧美激情麻豆| 国产精品专区h在线观看| 免费毛片一区二区三区久久久| 欧美福利在线观看| 久久激情视频| 欧美视频精品在线| 麻豆精品精品国产自在97香蕉| 欧美日韩不卡视频| 久久综合久久综合久久| 欧美另类99xxxxx| 美女露胸一区二区三区| 欧美视频国产精品| 欧美激情视频在线播放 | 免费成人av在线看| 亚洲欧美在线观看| 欧美激情一区二区三区| 老司机67194精品线观看| 欧美三级免费| 亚洲欧洲另类国产综合| 一区二区在线观看av| 亚洲网站视频| 一本色道婷婷久久欧美| 久久久精品动漫| 久久久久91| 国产精一区二区三区| 一本色道久久综合亚洲精品不卡| 亚洲国产精品电影| 久久久精品五月天| 久久激情视频久久| 国产欧美精品在线观看| 在线一区观看| 亚洲香蕉视频| 国产精品大片| 一区二区av在线| 亚洲一区二区av电影| 欧美日韩在线免费视频| 亚洲日韩视频| 亚洲视频一区二区免费在线观看| 欧美精品一区三区在线观看| 欧美激情综合色| 亚洲黑丝在线| 欧美凹凸一区二区三区视频| 欧美成人国产va精品日本一级| 国产一区白浆| 久久丁香综合五月国产三级网站| 久久久高清一区二区三区| 国产午夜精品福利| 久久精品国产视频| 欧美成人免费全部观看天天性色| 伊人久久综合97精品| 久久午夜精品| 亚洲片在线观看| 亚洲小视频在线| 国产日韩在线亚洲字幕中文| 欧美在线观看一区二区| 嫩草伊人久久精品少妇av杨幂| 亚洲国产合集| 欧美色视频在线| 午夜一区在线| 欧美护士18xxxxhd| 一区二区三区日韩欧美| 国产精品丝袜久久久久久app| 亚洲欧美日韩视频二区| 狼人社综合社区| 亚洲精品乱码视频| 国产精品二区在线观看| 午夜精品久久久久久久99水蜜桃| 久久美女性网| 一本色道久久88精品综合| 国产精品久久久久久久久久三级| 欧美一级午夜免费电影| 亚洲国产成人av在线| 亚洲一区在线免费观看| 精品51国产黑色丝袜高跟鞋| 欧美精品aa| 久久国产福利| 夜夜嗨av一区二区三区网页 | 亚洲精品在线观看视频| 国产精品日本精品| 久久综合九色综合网站| 在线一区免费观看| 欧美成人精品1314www| 亚洲欧美国产77777| 欲色影视综合吧| 国产精品成人v| 欧美 日韩 国产在线| 亚洲一区二区三区国产| 欧美激情一区三区| 久久精品噜噜噜成人av农村| 9久re热视频在线精品| 精品999成人| 国产女优一区| 国产精品扒开腿做爽爽爽视频| 久久综合中文字幕| 午夜精品久久久久久久| 亚洲精品网站在线播放gif| 久热这里只精品99re8久| 亚洲一区在线免费| 一本综合久久| 亚洲精品五月天| 亚洲国产va精品久久久不卡综合| 国产精品日韩专区| 欧美日韩在线视频首页| 欧美激情精品久久久久久| 久久看片网站| 欧美在线播放| 欧美一站二站| 午夜激情久久久| 亚洲在线观看视频网站| 一区二区三区四区国产精品| 亚洲电影免费观看高清完整版在线| 久久免费高清| 老牛嫩草一区二区三区日本| 久久精品首页| 久久蜜桃香蕉精品一区二区三区| 午夜久久资源| 欧美亚洲一级片| 欧美一级久久久| 欧美中文字幕精品| 欧美一区二区免费视频| 午夜精品一区二区三区四区| 亚洲欧美日韩中文视频| 亚洲在线成人精品| 香蕉成人久久| 欧美专区日韩专区| 久久久综合免费视频| 久久综合导航| 亚洲高清资源| 一区二区三区精品| 亚洲综合视频网| 久久国产精品毛片| 免费成人毛片| 欧美色精品在线视频| 国产精品日韩欧美大师| 国产亚洲精品aa午夜观看| 韩国欧美一区| 亚洲破处大片| 亚洲一区二区三区激情| 欧美亚洲一区二区三区| 久久综合婷婷| 亚洲第一色在线| 宅男精品视频| 欧美综合国产| 欧美精品www在线观看| 欧美成人高清视频| 亚洲国产精品尤物yw在线观看 | 久久久久久欧美| 久久久www成人免费无遮挡大片 | 亚洲综合99| 久久人人看视频| 亚洲日韩欧美视频一区| 亚洲一区二区在线| 久久婷婷国产麻豆91天堂| 欧美成人午夜| 国产亚洲欧美日韩美女| 亚洲激情第一区| 亚洲欧美色婷婷| 欧美国产精品| 欧美一区二区三区免费观看视频| 蜜臀91精品一区二区三区| 国产精品久久久一区麻豆最新章节 | 亚洲高清不卡av| 亚洲一区精品电影| 欧美成人精品1314www| 国产精品一区亚洲| 一本久久综合亚洲鲁鲁| 久久精品av麻豆的观看方式| 亚洲黄一区二区三区| 欧美一区二区高清在线观看| 欧美激情影院| 尤物精品在线| 久久久精彩视频| 亚洲视频精品在线|