NOIP2006年题解

1、int i,j,k,x,y,t,v,n,max;cinn;/输入能量珠子个数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;/比较得出最优情况，存储

2、进二维数组01234567891012345W 8 4 3 4 2V 2 5 5 3 2 数组中填的是对前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 进制的数，如果 S 至少可分成 2 段，则 S 所对应的二进制数又可以转换为上述的 2k 进制数 r 。 例：设 k=3 ， w=7 。则 r 是个八进制数（ 2 3 =8 ）。由于 w=7 ， 长度为 7 的 01 字符串按 3 位一段分，可分为 3 段（即 1 ， 3 ， 3 ，左边第一段只有一个二进制位），则满足条件的八 进制数有： 2 位数：高位为 1 ： 6 个（即 12 ， 13 ， 14 ， 15 ， 16 ， 17 ），高位为 2 ： 5 个， ，高位为 6 ： 1 个（即 67 ）。共 6+5+ +1=21 个。 3 位数：高位只能是