HDU 3516 DP 四边形不等式优化 Tree Construction-白红宇

HDU 3516 DP 四边形不等式优化 Tree Construction

阅读量：5460 次

发布时间：2019-06-15

本文共 1190 字，大约阅读时间需要 3 分钟。

设d(i, j)为连通第i个点到第j个点的树的最小长度，则有状态转移方程：

d(i, j) = min{ d(i, k) + d(k + 1, j) + p[k].y - p[j].y + p[k+1].x - p[i].x }

然后用四边形不等式优化之。。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
           6 #define MP make_pair 7 #define x first 8 #define y second 9 using namespace std;10 11 typedef pair
           
             PII;12 13 const int maxn = 1000 + 10;14 const int INF = 0x3f3f3f3f;15 int n;16 17 PII p[maxn];18 19 int d[maxn][maxn], s[maxn][maxn];20 21 int main()22 {23 while(scanf("%d", &n) == 1 && n)24 {25 for(int i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y);26 for(int i = 1; i <= n; i++)27 {28 s[i][i + 1] = i;29 d[i][i + 1] = p[i+1].x - p[i].x + p[i].y - p[i+1].y;30 }31 32 for(int l = 3; l <= n; l++)33 {34 for(int i = 1; i + l - 1 <= n; i++)35 {36 int j = i + l - 1;37 d[i][j] = INF;38 for(int k = s[i][j-1]; k <= s[i+1][j]; k++)39 {40 int t = d[i][k] + d[k+1][j] + p[k].y - p[j].y + p[k+1].x - p[i].x;41 if(t < d[i][j])42 {43 d[i][j] = t;44 s[i][j] = k;45 }46 }47 }48 }49 50 printf("%d\n", d[1][n]);51 }52 53 return 0;54 }