POJ 1160 Post Office (四边形不等式优化DP)

时间：2021-01-24 15:12:42

题意: 给出m个村庄及其距离，给出n个邮局，要求怎么建n个邮局使代价最小。

析：一般的状态方程很容易写出，dp[i][j] = min{dp[i-1][k] + w[k+1][j]}，表示前 j 个村庄用 k 个邮局距离最小，w可以先预处理出来O(n^2)，但是这个方程很明显是O(n^3)，但是因为是POJ，应该能暴过去。。= =，正解应该是对DP进行优化，很容易看出来，w是满足四边形不等式的，也可以推出来 s 是单调的，可以进行优化。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <cmath>

#include <stack>

#include <sstream>

#define debug() puts("++++");

#define gcd(a, b) __gcd(a, b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define freopenr freopen("in.txt", "r", stdin)

#define freopenw freopen("out.txt", "w", stdout)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 1e16;

const double inf = 0x3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int maxn = 300 + 10;

const int mod = 1e9 + 7;

const int dr[] = {-1, 0, 1, 0};

const int dc[] = {0, 1, 0, -1};

const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};

int n, m;

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

inline bool is_in(int r, int c){

  return r >= 0 && r < n && c >= 0 && c < m;

}

int dp[35][maxn], w[maxn][maxn], s[35][maxn];

int a[maxn];

int main(){

  while(scanf("%d %d", &n, &m) == 2){

    for(int i = 1; i <= n; ++i)  scanf("%d", a+i);

    for(int i = 1; i <= n; ++i){

      w[i][i] = 0;

      for(int j = i+1; j <= n; ++j)

        w[i][j] = w[i][j-1] + a[j] - a[i+j>>1];

    }

    memset(dp, INF, sizeof dp);

    memset(s, 0, sizeof s);

    for(int i = 1; i <= n; ++i)  dp[1][i] = w[1][i];

    for(int i = 2; i <= m; ++i){

      s[i][n+1] = n;

      for(int j = n; j >= i; --j)

        for(int k = s[i-1][j]; k <= s[i][j+1]; ++k)

          if(dp[i][j] > dp[i-1][k] + w[k+1][j]){

            dp[i][j] = dp[i-1][k] + w[k+1][j];

            s[i][j] = k;

          }

    }

    printf("%d\n", dp[m][n]);

  }

  return 0;

}

　　

相关文章