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 huicpc035 at 2008-05-09 19:03:17 on Problem 3593
In Reply To:为什么和单个物品个数上限有关系? Posted by:alpc117 at 2008-05-09 17:59:35
我开四维数组dis[10][maxn][10][maxn];maxn表示单个种类物品最多数量;
dis[i][idi][j][idj]表示第i种物品的第idi个与第j个物品的第idj个的平面最短距离,先预处理求出这些距离后再求解,由于maxn必须开到单个物品最大数量上限大小,所以我的方法就必须知道最大单个物品数量上界,如果不知时便必须开到dis[10][20*20][10][20*20].
怕这种情况
20 20 1 X
*AAAAA....
AAAAAA....
..........
不知alpc117有何其他方法,请告诉我或给点提示,我下午还在想可不可以更进一步优化或用别的方法,这次比赛我就是吃亏在老AC了了事,做题不想题,这题我以前写过类似的,当时BFS+DFS过了就没管,结果比赛就.......
请提示一下有何更好的方法...........

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