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

虽然用dp ac了,可是每次只扩展一个邮局,这个思路好难想。

Posted by lynxpengpeng at 2008-05-26 19:11:17 on Problem 1160 and last updated at 2008-05-26 19:12:15
用 i 表示可利用邮局数,j 表示村子的数,开始填表,cost[i][j]表示只设一个邮局的距离
 for(int i = 2;i <= n;i++)  
    for(int j = i;j <= m;j++)
    {
	for(int k = 1; k <= j - 1 ; k++) //从k 开始分成两部分
	{
	   if(re[i-1][k] + cost[k+1][j] < re[i][j] )
	   {
	      re[i][j] = re[i-1][k] + cost[k+1][j] ;
	   }
        }
		   
    }
不知道除了这种,还有没有别的dp 递归式,谢谢了。


----我是菜鸟中的菜鸟

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