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

能贪心么? 按最大间隔把路分成 p 段

Posted by sunmoonstar_love at 2006-07-22 12:46:45 on Problem 1160
In Reply To:DP,Why WA, Posted by:lookus at 2004-10-01 13:56:56
> 好像没问题啊,我查了好几次啦
> 
> #include <stdio.h>
> #include <string.h>
> int n,m;
> int x[301];
> void main()
> {
> 	int i,j,k,l,tm;
> 	int p[301][301],q[301][31];
> 	////p[i][j] 表示村庄i到j间修一个邮局的最小花费。
> 	////q[i][j] 表示前i个村庄修j个邮局的最小花费
> 	scanf("%d%d",&n,&m);
> 	memset(q,0,sizeof(q));
> 	for(i=0;i<n;i++)
> 		scanf("%d",&x[i]);
> 	memset(p,0,sizeof(p));
> 	for(i=0;i<n;i++)
> 		for(j=i+1;j<n;j++)
> 		{
> 			l = i+(j-i)/2;
> 			for(k=i;k<l;k++)
> 				p[i][j] += (x[l]-x[i]);
> 			for(k=l+1;k<=j;k++)
> 				p[i][j] += (x[k]-x[l]);
> 		}
> 	for(i=0;i<n;i++)
> 		q[i][1] = p[0][i];
> 	for(i=0;i<n;i++)
> 		for(j=2;j<=m;j++)
> 		{
> 			q[i][j] = 2000000000;
> 			for(k=j-2;k<i;k++)
> 			{
> 				tm = q[k][j-1] + p[k+1][i];
> 				if(tm<q[i][j])
> 					q[i][j] = tm;
> 			}
> 		}
> 		printf("%d\n",q[n-1][m]);
> }

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