2490 - 邮局
高速公路旁有一定数量的村庄。高速公路可被视为一整数轴，村庄位置与整数坐标对应。没有两个村庄在同一坐标上，两村庄的距离为坐标差的绝对值。现将邮局建在村庄上，即表示邮局与村庄有相同的位置。构建过程中，邮局的位置应使得所有村庄与其最近邮局的距离之和最小。
编写一程序，用给定位置的村庄和邮局数量，计算出村庄与其最近邮局的距离和的最小值。
Input
程序从标准输入读取。
第一行包含一个整数tcase，表示测试组数。
每组输入数据占两行。
第1行包含两个整数:村庄V（V < = 300）和邮局P的数量（1 < = P < = 30,P < = V ）.
第2行包含V个整数，即村庄的位置X（1 < = X < = 10000）
Output
每行包括一个整数，即距离和的最小值。
Examples
Input
1 10 5 1 2 3 6 7 9 11 22 44 50
Output
9
Solution C
#include <stdio.h> #include<math.h> int INF = ~0U>>1; int w[305][305]={0}; int dp[305][35]; int a[305],V,P; void Init(int a[],int n) { int i,j; for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) w[i][j] = w[i][j-1] + a[j] - a[(i+j)>>1]; } int min(int a,int b) { if(a<b) return a; else return b; } int Work() { int i,j,k; for(i=1;i<=V;i++) { dp[i][i] = 0; dp[i][1] = w[1][i]; } for(j=2;j<=P;j++) { for(i=j+1;i<=V;i++) { dp[i][j] = INF; for(k=j-1;k<i;k++) dp[i][j] = min( dp[i][j] , dp[k][j-1] + w[k+1][i]); } } return dp[V][P]; } int main() { int i,tcase; scanf("%d",&tcase); while(tcase--) { scanf("%d%d",&V,&P); for(i=1;i<=V;i++) scanf("%d",&a[i]); Init(a,V); printf("%d\n",Work()); } return 0; }
Solution C++
#include <iostream> #include <string.h> using namespace std; int cost[302][302]; int res[302][302]; int village[302]; inline int myabs(int a) {return a>0?a:-a;} int main(){ int V,P,mid; int tcase; cin>>tcase; while(tcase--){ cin>>V>>P; for (int i=1;i<=V;i++) cin>>village[i]; //cost 初始化 memset(res,0,sizeof(res)); memset(cost,0,sizeof(cost)); for (int i=1;i<=V;i++){ for (int j=i;j<=V;j++){ mid=(i+j)>>1; for (int k=i;k<=j;k++) cost[i][j] +=myabs(village[mid]-village[k]); } } //res[i][j] 表示前i个邮局覆盖前j个村庄的最小代价 for (int i=1;i<=V;i++) res[1][i]=cost[1][i]; for (int i=2;i<=P;i++){ for (int j=1;j<=V;j++){ for (int k=1;k+j<=V;k++){ if(res[i][j+k]>res[i-1][j]+cost[j+1][j+k] || res[i][j+k]==0) res[i][j+k]=res[i-1][j]+cost[j+1][j+k]; } } } cout<<res[P][V]<<endl; } return 0; }