首页 > 代码库 > noi 162 post office dp
noi 162 post office dp
大致题意：
有v个村庄，每个村庄有各自的位置，且每个位置互不相同。现在要在村庄上设立P个邮局，使每个村庄到最近的邮局的距离之和最小。
分析：
定义状态d[i][j]表示前i个村庄，在这i个村庄中设立j个邮局的最小距离。s[i][j]表示村庄i至村庄j这几个村庄中设立一个邮局的最小距离。如果设立一个邮局，那么邮局设立在(a+b)/2这个位置是最优的。所以可以分解成以下子问题：
d[i][j]的最小值为d[k][j-1]的最小值加上s[k+1][i]，s[k+1][i]为在k+1至i这几个村庄中设立一个邮局的最小距离。
d[i][j]=min(d[i][j], d[k][j-1]+s[k+1][i])
边界条件d[i][1]=s[1][i].
s数组可做如下优化：
s[1][4]，把邮局设立在2和设立在3上距离是相同的。x2-x1+x3-x2+x4-x2与x3-x1+x3-x2+x4-x3相等。s[1][5]是把邮局设立在3上，s[1][5]=s[1][4]+x[5]-x[3]。由此，可得出递推式：s[i][j]=s[i][j-1]+x[j]-x[(i+j)/2].
#include <iostream>#include <cstdio>using namespace std;const int INF=1e8;int x[305];int d[305][35];int s[305][305];int main(){ //freopen("in.txt","r",stdin); int n,p; while(~scanf("%d%d",&n,&p)) { for(int i=1;i<=n;i++) scanf("%d",&x[i]); for(int i=1;i<=n;i++) for(int j=1;j<i && j<=p;j++) d[i][j]=INF; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) s[i][j]=s[i][j-1]+x[j]-x[(i+j)/2]; d[i][1]=s[1][i]; } for(int i=2;i<=n;i++) for(int j=2;j<=i && j<=p;j++) for(int k=j-1;k<i;k++) d[i][j]=min(d[i][j],d[k][j-1]+s[k+1][i]); printf("%d\n",d[n][p]); } return 0;}
noi 162 post office dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。