hdu3516(dp四边形优化)

本文主要是介绍hdu3516(dp四边形优化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：点击打开链接

题意：给定一些点(xi,yi)(xj,yj)满足:i<j,xi<xj,yi>yj。用下面的边连起来，使得所有边的长度最小

代码：

<span style="font-family:FangSong_GB2312;font-size:18px;">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int x[1005],y[1005],s[2005][2005],dp[2005][2005];
int main(){int n,i,j,k,l,ans;while(scanf("%d",&n)!=EOF){memset(dp,INF,sizeof(dp));for(i=1;i<=n;i++){scanf("%d%d",&x[i],&y[i]);dp[i][i]=dp[i+n][i+n]=0;s[i][i]=i,s[i+n][i+n]=i+n;}for(l=2;l<=2*n;l++){                    //四边形优化，很石子合并一样for(i=1;i<=2*n-l+1;i++){            //注意每次合并的增加量j=i+l-1;for(k=s[i][j-1];k<=s[i+1][j];k++){if(dp[i][j]>dp[i][k]+dp[k+1][j]+(y[k]-y[j])+(x[k+1]-x[i])){dp[i][j]=dp[i][k]+dp[k+1][j]+(y[k]-y[j])+(x[k+1]-x[i]);s[i][j]=k;}}}}printf("%d\n",dp[1][n]);}return 0;
}
</span>

这篇关于hdu3516(dp四边形优化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---