首页 > 代码库 > POJ1160
POJ1160
再次使用强大的四边形优化dp
f[i][j]=max(f[k][j-1]+w[k+1][i])
其中f[i][j]表示前i个村落有j个邮电局，w[i][j]表示[i,j]区间上安装一个邮电局最短路径和
其中w[i][j]邮电局必然是安装在(i+j)/2（中位数）的村落中，若(i+j)/2不为整数，则中间两个村落都可以。证明可以看《算法导论》
至于四边形不等式，这次，可以直接容易得到 s[i][j-1]<=s[i][j]<=s[i+1][j] 稍微证明下就可以出来，凭感觉都是对的。
#include <cstdio>#include <cstring>#define min(x,y) (x>y?y:x)int v,p,a[305],sum[305],w[305][305],f[305][35],s[305][35];int main(){ memset(f,127,sizeof(f)); scanf("%d%d",&v,&p); for(int i=1; i<=v; i++){ scanf("%d",&a[i]); sum[i]=a[i]+sum[i-1]; } for(int i=1; i<=v; i++){ w[i][i]=0; for(int j=i+1; j<=v; j++){ w[i][j]=sum[j]-sum[(i+j)/2]-sum[(i+j)/2-1]+sum[i-1]; if((i+j)%2!=0) w[i][j]-=a[(i+j)/2]; } } for(int i=1; i<=v; i++) f[i][1]=w[1][i]; for(int j=2; j<=p; j++){ s[v+1][j]=v-1; for(int i=v; i>=j; i--) { for(int k=s[i][j-1]; k<=s[i+1][j]; k++) if(f[i][j]>f[k][j-1]+w[k+1][i]) { f[i][j]=f[k][j-1]+w[k+1][i]; s[i][j]=k; } } } printf("%d",f[v][p]); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。