用 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 递归式，谢谢了。


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

• Re:虽然用dp ac了，可是每次只扩展一个邮局，这个思路好难想。 (382) DestinyDesigner 2008-10-24 18:09:36
  • Re:虽然用dp ac了，可是每次只扩展一个邮局，这个思路好难想。 (10) DestinyDesigner 2008-10-24 18:09:58