首页 > 代码库 > 【四边形不等式】POJ1160[IOI2000]-Post Office
【四边形不等式】POJ1160[IOI2000]-Post Office
【题目大意】
v个村庄p个邮局，邮局在村庄里，给出村庄的位置，求每个村庄到最近邮局距离之和的最小值。
【思路】
四边形不等式，虽然我并不会证明:(
dp[i][j]表示前i个村庄建j个邮局的最小值，w[i][j]表示在i到j之间建立一个邮局的最小值。w[i][j]显然取i~j的中位数，可以在O(1)时间内求出。
显然dp[i][j]=min{dp[k][j-1]+w[k+1][i]}。
傻傻写错i和j……
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int MAXV=305; 8 const int MAXP=35; 9 const int INF=0x7fffffff;10 int v,p;11 int dis[MAXV],sum[MAXV],w[MAXV][MAXV];//w[i][j]表示在[i,j]间建立一个邮局的最小代价 12 int s[MAXV][MAXP],dp[MAXV][MAXP];13 14 void init()15 {16 scanf("%d%d",&v,&p);17 sum[0]=0;18 for (int i=1;i<=v;i++) scanf("%d",&dis[i]);19 sort(dis+1,dis+v+1);20 for (int i=1;i<=v;i++) sum[i]=dis[i]+sum[i-1];21 for (int i=1;i<=v;i++)22 {23 w[i][i]=0;24 for (int j=i+1;j<=v;j++)25 {26 if ((i+j)%2==0) w[i][j]=sum[j]-sum[(i+j)/2]-sum[(i+j)/2-1]+sum[i-1];27 else w[i][j]=sum[j]-sum[(i+j)/2]-sum[(i+j)/2-1]+sum[i-1]-dis[(i+j)/2];28 }29 }30 }31 32 void solve()33 {34 memset(dp,127,sizeof(dp));35 for (int i=1;i<=v;i++) dp[i][1]=w[1][i];36 for (int j=2;j<=p;j++)37 {38 s[v+1][j]=v-1;39 for (int i=v;i>=j;i--)40 {41 for (int k=s[i][j-1];k<=s[i+1][j];k++)42 {43 if (dp[i][j]>dp[k][j-1]+w[k+1][i])//一开始这里敲成了w[k+1][j] 44 {45 dp[i][j]=dp[k][j-1]+w[k+1][i];46 s[i][j]=k;47 }48 }49 } 50 }51 printf("%d",dp[v][p]); 52 }53 54 int main()55 {56 init();57 solve(); 58 return 0; 59 }
【四边形不等式】POJ1160[IOI2000]-Post Office
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。