随笔-68  评论-10  文章-0  trackbacks-0
DP .首先求出任意两个村庄间(包括端点)建一个邮局后,到邮局的最短距离和,记为min_dis[i][j],当邮局建到中点时min_dis[i][j]最小. 用f[i][j]表示前i个邮局建在前j个村庄.则f[i][j]=min{f[i-1][k]+min_dis[k+1][j],i-1<=k<j}.见代码:
#include<iostream>
using namespace std;
int v,p;
int vill[305];
int f[35][305];
int min_dis[305][305];

int main()
{
    
int i,j,k;
    scanf(
"%d%d",&v,&p);
    
for(i=1;i<=v;i++)
    scanf(
"%d",&vill[i]);
    memset(min_dis,
0,sizeof(min_dis));
    
for(i=1;i<=v;i++)
    
for(j=i+1;j<=v;j++)
    
{
        
int mid=(i+j)/2;
        
for(k=i;k<mid;k++)
        
{
            min_dis[i][j]
+=vill[mid]-vill[k];
        }

        
for(k=mid+1;k<=j;k++)
        
{
            min_dis[i][j]
+=vill[k]-vill[mid];
        }

    }

    
for(i=1;i<=v;i++) f[1][i]=min_dis[1][i];
    
for(i=2;i<=p;i++)
    
for(j=i;j<=v;j++)
    
{
        
int minn=100000000;
        
for(k=i-1;k<=j-1;k++)
        
{
            
if(f[i-1][k]+min_dis[k+1][j]<minn)
            minn
=f[i-1][k]+min_dis[k+1][j];
        }

        f[i][j]
=minn;
    }

    
    printf(
"%d\n",f[p][v]);
    
//system("pause");
    return 0;
}

posted on 2010-08-19 12:45 wuxu 阅读(164) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理