Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

对决策数量的优化

Posted by lovai at 2010-11-26 14:19:40 on Problem 1260
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator