政府在某山区修建了一条道路,恰好穿越总共m个村庄的每个村庄一次,没有回路或交叉,任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di(为正整数),其中,0<i<m。为了提高山区的文化素质,政府又决定从m个村中选择n个村建小学(设0<n≤m<500)。请根据给定的m、n以及所有相邻村庄的距离,选择在哪些村庄建小学,才使得所有村到最近小学的距离总和最小,计算最小值。
F [ i] [j ]= min{ f[k][j-1] + c[k+1][i] }
#include "bits/stdc++.h" using namespace std; #define N 1003 int m,n,a[N],c[N][N],f[N][N],p[N][N]; void print_path(int i, int j){ if (i <= 0) return; int k = p[i][j]; print_path(k,j-1); if (k + 1 == i) printf("Depot %d at restaurant %d serves restaurant %d\n", j, (k + 1 + i) >> 1, k+ 1); else printf("Depot %d at restaurant %d serves restaurants %d to %d\n", j, (k + 1 + i) >> 1, k + 1, i); } void sov(int cas){ int i,j,k; for(i=1;i<=n;i++) cin>>a[i] ; for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) c[i][j]=c[i][j-1]+a[j]-a[(i+j)/2]; memset(f,127,sizeof f); for(i=1;i<=n;i++) f[i][1]=c[1][i]; for(i=2;i<=n;i++) for(j=2;j<=m&&j<=i;j++) for(k=j-1;k<i;k++){ int t =f[k][j-1]+c[k+1][i]; if(f[i][j]>t) p[i][j]=k,f[i][j]=t; } printf("Chain %d\n",cas); print_path(n,m); printf("Total distance sum = %d\n\n",f[n][m]); //cout<<f[n][m]<<endl; } signed main(){ int cas=0; while(cin>>n>>m){ if(n==0&&m==0) break; sov(++cas); } }
标签:cas,Food,662,Fast,int,村庄,printf,UVA From: https://www.cnblogs.com/towboa/p/17351152.html