Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
对决策数量的优化1)不能将同等级的珍珠分到两个或更多个等级来购买。 2)当前珍珠只能与比它等级低(左边的)的若干个连续的等级的珍珠合并。 3) 这些连续的珍珠如果存在一个与当前珍珠合并不划算,那么其左边的所有珍珠(包括它本身)都不能对当前解进行优化,可以剪枝掉,那么现在就是要找到最右边的不划算的珍珠并对其右边(包括本身)进行剪枝 主要代码+对3结论的证明 op[1]=(a[1]+10)*p[1]; for(i=2;i<=n;i++) { op[i]=op[i-1]+(a[i]+10)*p[i]; fa=a[i]; //(a[j+1]+fa+10)*p[i]<(a[j+1]+10)*p[j+1]+(fa+10)*p[i] ==> //a[j+1]*p[i]<(a[j+1]+10)*p[j+1]==>称a[j+1]<L(i,j+1) //若从左边的第j+1个到i合并后不划算,即 a[j+1]<L(i,j+1),那么即使在0~j之间存在k满足a[k]<L(i,k)的也不会使op[i]减小 //证明 设k为从i向左第一个划算的(多个划算的也同样可证) a[k]<L(i,k)<L(i,j+1) 所以j+1也可以和k进行合并,而且比和i合并更优 //(a[j+1]+10)*p[j+1]<a[j+1]*p[i]现在试图把k~j+1之间的所有元素作为一个元素进行加入 // 即比较(a[k]+a[k+1]+…+a[j+1]+10)*p[j+1]与(a[k]+a[k+1]+…+a[j+1])*p[i] // 易证(a[k]+a[k+1]+…+a[j+1]+10)*p[j+1]<(a[k]+a[k+1]+…+a[j+1])*p[i] // 所以这样的加入也是不划算的 for(j=i-2;( a[j+1]*p[i]<(a[j+1]+10)*p[j+1] )&&j>=0;j--){ fa+=a[j+1]; t=op[j]+(fa+10)*p[i]; if(op[i]>t) op[i]=t; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator