NOIP2006年題解

1、int i,j,k,x,y,t,v,n,max;cinn;/輸入能量珠子個數(shù)for(i=1;iv; /輸入能量珠子頭標記bi.head=v;if(i=1) bn.rear=v;elsebi-1.rear=v;/頭標記入表并且尾標記入表dpi1=0;for(j=2;j=n;j+)/ j代表有幾個珠子合并for(i=1;i=n;i+)/枚舉起始點 for(dpij=0,k=1;kn) x=x-n;y=x+(j-k)-1;if(yn)y=y-n;t=dpik+dpxj-k+bi.head*bx.head*by.rear;/一串項鏈內的各種情況if(tdpij) dpij=t;/比較得出最優(yōu)情況，存儲

2、進二維數(shù)組01234567891012345W 8 4 3 4 2V 2 5 5 3 2 數(shù)組中填的是對前i件物品，花費不超過010，價格與重要度乘積的總和的最大值。例如： a(3,7)中填的是“對于前3件物品，花費不超過7，價格與重要度乘積的總和的最大值”0123456789101000000001616162345W 8 4 3 4 2V 2 5 5 3 2 I=1，即對前1件物品，花費不超過010，價格與重要度乘積的總和的最大值分別是：01234567891010000000016161620000345W 8 4 3 4 2V 2 5 5 3 2 i=2，即對前i件物品，花費不超過k(

3、0=k=10)，價格與重要度乘積的總和的最大值分別是：If k=wi then 第i件物品可要可不要，不要ai,k:=ai-1,k； 要 ai,k:=ai-1,k-wi+wi*vi ai,k:=max(ai-1,k, ai-1,k-wi+wi*vi)01234567891010000000016161620000? ?345W 8 4 3 4 2V 2 5 5 3 2 If k=w2 then 第i件物品可要可不要，不要a2-1,4=a1,4=0； 要 a2-1,4-w2+w2*v2=a1,0+4*5=20max(a2-1,k, a2-1,k-w2+w2*v2)=max(0,20)012345

4、678910100000000161616200002020345W 8 4 3 4 2V 2 5 5 3 2 If k=w2 then 第i件物品可要可不要，不要a2-1,4=a1,4=0； 要 a2-1,4-w2+w2*v2=a1,0+4*5=20max(a2-1,k, a2-1,k-w2+w2*v2)=max(0,20)012345678910100000000161616200002020202020202020345W 8 4 3 4 2V 2 5 5 3 2 If k=w2 then 第i件物品可要可不要，不要a2-1,k=a1,k=0； 要 a2-1,k-w2+w2*v2=a1,

5、k-4+4*5=20max(a1,k, a1,k-4+20)0123456789101000000001616162000020202020202020203000152020203535353545W 8 4 3 4 2V 2 5 5 3 2 If k=w3 then 第i件物品可要可不要，不要a3-1,k=a2,k； 要 a3-1,k-w3+w3*v3=a2,k-3+3*5max(a2,k, a2,k-3+15)01234567891010000000016161620000202020202020202030001520202035353535400015202020353535355W

6、 8 4 3 4 2V 2 5 5 3 2 If k=w4 then 第i件物品可要可不要，不要a4-1,k=a3,k； 要 a4-1,k-w4+w4*v4=a3,k-4+4*3max(a3,k, a3,k-4+12)012345678910100000000161616200002020202020202020300015202020353535354000152020203535353550041520202435353939W 8 4 3 4 2V 2 5 5 3 2 If k=w5 then 第i件物品可要可不要，不要a5-1,k=a4,k； 要 a5-1,k-w5+w5*v5=a4,

7、k-2+2*2max(a4,k, a4,k-2+4)012345678910100000000161616200002020202020202020300015202020353535354000152020203535353550041520202435353939W 8 4 3 4 2V 2 5 5 3 2 對于這5件物品，花費不超過10，價格與重要度乘積的總和的最大值是：a(5,10)即39我們再從另一角度作些解釋：設 S 是長度為 w 的 01 字符串（即字符串 S 由 w 個 “ 0 ” 或 “ 1 ” 組成）， S 對應于上述條件（ 3 ）中的 q 。將 S 從右起劃分為若干個長度為 k 的段，每段對應一位 2k 進制的數(shù)，如果 S 至少可分成 2 段，則 S 所對應的二進制數(shù)又可以轉換為上述的 2k 進制數(shù) r 。 例：設 k=3 ， w=7 。則 r 是個八進制數(shù)（ 2 3 =8 ）。由于 w=7 ， 長度為 7 的 01 字符串按 3 位一段分，可分為 3 段（即 1 ， 3 ， 3 ，左邊第一段只有一個二進制位），則滿足條件的八 進制數(shù)有： 2 位數(shù)：高位為 1 ： 6 個（即 12 ， 13 ， 14 ， 15 ， 16 ， 17 ），高位為 2 ： 5 個， ，高位為 6 ： 1 個（即 67 ）。共 6+5+ +1=21 個。 3 位數(shù)：高位只能是