首页 > 代码库 > 【poj1160】 Post Office
【poj1160】 Post Office
http://poj.org/problem?id=1160 (题目链接)
题意
按照递增顺序给出一条直线上坐标互不相同的n个村庄，要求从中选择p个村庄建立邮局，每个村庄使用离它最近的那个邮局，使得所有村庄到各自所使用的邮局的距离总和最小。
Solution
经典dp方程：
其中f[i][j]表示前j个村庄，放置i个邮局的最优方案。w[i][j]表示在i到j的村庄放置一个邮局，i~j的村庄到这个邮局的总距离。考虑如何求解w[i][j]，因为只放置一个邮局，所以一定是放在最中间的那个点上，所以邮局两侧的点到邮局的的距离之和就为它们两点之间的距离，然后从两边向中间扫描一遍更新答案就可以了。于是我们就得到了O(n*n*n*p)的做法。
考虑四边形不等式优化。像dp方程长成形如“合并石子”那个样子的，很多都可以用四边形不等式优化。然而通过四边形不等式证明决策单调性实在是繁琐爆炸，看了一晚上感觉就是不停的放缩不等式强行证明。。其实当你感觉可以四边形不等式优化的时候，最有效的做法就是写个普通dp再写个优化后的dp进行对拍(→_→反正dp短)。
于是经过四边形不等式优化后它的决策就神奇的具有单调性了→_→。设s[i][j]表示f[i][j]的决策方案。那么s[i-1][j]<=s[i][j]<=s[i][j+1]。所以我们枚举k的时候就不用从头枚到尾了，直接从s[i-1][j]枚到s[i][j+1]就可以了，所以复杂度就变成了O(n*n*p)。也许还有论文所说的O(n*p)的做法，就是把w[i][j]O(n)预处理，然而这如何O(n)预处理呢，我只会n²。。。
代码
// poj1160#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define MOD 998244353#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;inline LL getint() { int f,x=0;char ch=getchar(); while (ch<=‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1;else f=1;ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int maxn=500;int f[maxn][maxn],sum[maxn][maxn],s[maxn][maxn],a[maxn];int n,p;int dis(int i,int j) { if (i>=j) return 0; if (sum[i][j]!=0) return sum[i][j]; int x=i,y=j; while (x<y) sum[i][j]+=a[y--]-a[x++]; return sum[i][j];}int main() { while (scanf("%d%d",&n,&p)!=EOF) { for (int i=1;i<=n;i++) scanf("%d",&a[i]); memset(f,0,sizeof(f)); memset(sum,0,sizeof(sum)); for (int i=1;i<=n;i++) f[1][i]=dis(1,i),s[i][i]=i-1; for (int i=2;i<=p;i++) { s[i][n+1]=n-1; for (int j=n;j>=i;j--) { f[i][j]=inf; for (int k=s[i-1][j];k<=s[i][j+1];k++) if (f[i-1][k]+dis(k+1,j)<f[i][j]) f[i][j]=f[i-1][k]+dis(k+1,j),s[i][j]=k; } } printf("%d\n",f[p][n]); } return 0;}
【poj1160】 Post Office
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。