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

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 流牛ζ木馬 閱讀(4092) 評論(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   管理


<2009年3月>
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

導航

統計

公告

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>
            久久本道综合色狠狠五月| 欧美成人在线网站| 亚洲欧美在线aaa| 亚洲激情成人| 国内激情久久| 国产欧美日韩在线视频| 欧美日韩美女在线| 欧美视频在线观看| 国产精品国产三级国产专播精品人| 欧美激情亚洲国产| 欧美日韩国产va另类| 欧美伦理a级免费电影| 欧美少妇一区二区| 国产精品丝袜久久久久久app| 国产欧美视频一区二区三区| 国产一区二区三区成人欧美日韩在线观看 | 欧美在线视频免费观看| 亚洲免费在线电影| 久久久综合精品| 亚洲高清中文字幕| 嫩草影视亚洲| 日韩网站在线观看| 亚洲综合色丁香婷婷六月图片| 亚洲欧美成aⅴ人在线观看| 久久久www| 亚洲国产另类久久久精品极度| 久久福利视频导航| 久久久综合网站| 欧美理论电影网| 国产日韩亚洲| 亚洲精品久久久久久久久久久久| 一本色道久久综合亚洲91 | 久久久九九九九| 欧美二区在线看| 一区二区三区精品在线| 久久成人免费| 国产精品国产三级国产专区53| 国产精品视频内| 亚洲电影欧美电影有声小说| 亚洲一级片在线观看| 蜜臀91精品一区二区三区| 亚洲激情视频网站| 欧美在线视频a| 欧美日韩在线不卡一区| 一区二区在线观看av| 在线视频免费在线观看一区二区| 欧美一区二区三区精品| 91久久久久久久久久久久久| 久久精品综合网| 国产精品羞羞答答| 亚洲免费小视频| 亚洲日本乱码在线观看| 久久精品一区二区三区不卡| 国产精品卡一卡二卡三| 日韩视频一区二区三区在线播放| 先锋亚洲精品| 99国内精品| 欧美日本精品在线| 99精品国产99久久久久久福利| 免费在线成人av| 久久精品欧美日韩| 狠狠色狠狠色综合日日91app| 欧美在线综合视频| 亚洲中字在线| 国产日韩欧美视频在线| 午夜精品久久久久久| 亚洲午夜女主播在线直播| 欧美三级韩国三级日本三斤| 亚洲一级片在线看| 亚洲欧美国产制服动漫| 国产精品中文字幕欧美| 欧美在线国产精品| 校园春色国产精品| 韩国三级电影一区二区| 久久一二三国产| 猛男gaygay欧美视频| 亚洲欧洲日本一区二区三区| 亚洲二区免费| 欧美亚日韩国产aⅴ精品中极品| 国产精品网站在线观看| 欧美在线看片| 在线观看日韩专区| 欧美日韩国产成人在线| 欧美日韩国产美| 日韩亚洲不卡在线| 99视频一区| 国产精品你懂的| 久久久久国产成人精品亚洲午夜| 欧美一区二区黄| 亚洲丶国产丶欧美一区二区三区| 亚洲二区视频| 欧美视频在线一区二区三区| 亚洲女女做受ⅹxx高潮| 羞羞色国产精品| 亚洲国产精品黑人久久久| 欧美成人免费全部观看天天性色| 欧美不卡三区| 午夜精品福利一区二区蜜股av| 久久本道综合色狠狠五月| 在线日韩一区二区| a91a精品视频在线观看| 国产精品国产| 亚洲尤物在线| 久久精品91久久久久久再现| 久热精品视频在线观看一区| 亚洲二区视频| 国产精品免费观看视频| 免费在线欧美视频| 一区二区高清视频| 亚洲国产精品激情在线观看| 久久露脸国产精品| 久久精品国产精品亚洲| 中文国产一区| 亚洲另类在线一区| 一区国产精品| 精品999网站| 国产欧美一区二区色老头| 欧美激情中文不卡| 老妇喷水一区二区三区| 久久综合给合| 欧美成人在线免费观看| 亚洲专区一区二区三区| 久久久精品五月天| 亚洲一级在线观看| 久久精品五月| 亚洲欧美日韩一区| 欧美激情一区二区三区成人| 久久经典综合| 欧美激情国产高清| 久久激情五月激情| 国产精品女人网站| 999亚洲国产精| 亚洲国产成人精品女人久久久| 久久综合99re88久久爱| 欧美va天堂va视频va在线| 久久激五月天综合精品| 亚洲国产你懂的| 久久久久久网址| 久久精品国内一区二区三区| 国产精品高潮呻吟久久av黑人| 亚洲第一页自拍| 在线观看亚洲a| 久久久久久尹人网香蕉| 久久激情婷婷| 国产亚洲欧美一区二区| 一区二区三区色| 欧美精品久久久久久久免费观看| 美女网站在线免费欧美精品| 国产亚洲精品成人av久久ww| 亚洲综合色在线| 欧美在线不卡视频| 国产日韩欧美高清| 久久精品天堂| 欧美激情导航| 亚洲最新色图| 国产精品久久久| 欧美亚洲尤物久久| 噜噜噜躁狠狠躁狠狠精品视频| 永久免费毛片在线播放不卡| 久久综合一区二区| 91久久久一线二线三线品牌| 亚洲尤物视频网| 韩日精品视频| 欧美成年人视频网站| 亚洲欧洲一区二区三区| 亚洲一区二区免费看| 国产精品资源| 久久福利资源站| 亚洲人体1000| 欧美亚洲一区二区三区| 国产一区二区三区在线观看网站| 久久天堂成人| 亚洲精品中文字| 欧美一二三区在线观看| 在线观看成人av| 欧美日韩综合在线| 欧美在线视频在线播放完整版免费观看| 久久久精品性| 99这里只有精品| 国产一区二区三区网站| 裸体丰满少妇做受久久99精品| 亚洲精品视频免费| 欧美在线看片| 日韩网站在线观看| 国内激情久久| 国产精品福利在线| 看欧美日韩国产| 亚洲影院污污.| 亚洲国产另类精品专区| 欧美伊人久久| 一区二区三区国产精品| 国产自产女人91一区在线观看| 欧美精品999| 久久久夜夜夜| 亚洲一区尤物| 99精品国产在热久久| 欧美va亚洲va香蕉在线| 欧美一区二区高清在线观看| 日韩亚洲在线| 亚洲国产精品成人va在线观看|