luogu 4647 邮局

分析

Part 1 状态

村庄，邮局，嗯没了

dp[i][j]表示前i个村庄j个邮局，至于需不需要当前村庄的状态，待定

再看看题意，发现其实p个邮局像是把村庄分成了p+1个互不影响的区域

Part 2 转移

dp[i][j]的转移，直接由dp[i-1]转移吗？

不行，这样的话你需要考虑是否在i建邮局，而建邮局又是一个区间的问题，如果没有办法记录方案，最好还是不要这样转移

那么，由j-1转移？我们不用管i是否建邮局，既然p个邮局像是把村庄分成了p+1个互不影响的区域，不如我们就这个区域来考虑

i我们可以不将他考虑为区间的中间部分，而是考虑为结尾

开头？这个好说，枚举就好

于是，原始方程：

dp[i][j] = max(dp[i][j],dp[k][j-1]+cost[k+1][i])

cost[k+1][i]表示在[k+1,i]这个区间建一个邮局的最小代价，可以初始化

建在哪里？当然是建在中点最划算，画图看看就好

看朴素的求法：

思考一下，完全可以用前缀和优化到n²嘛

好了，不过转移好像也是n³的，怎么优化呢？

还记得四边形优化吗？

自己看证明：

题解1

题解2

代码

 1 /**********************
 2 User：Mandy.H.Y
 3 Languge:c++
 4 Problem:luogu4647
 5 Algorithm: 
 6 **********************/
 7 #include<bits/stdc++.h>
 8 
 9 using namespace std;
10 
11 const int maxn = 3005;
12 const int maxp = 305;
13 
14 int n,p;
15 int a[maxn];
16 int dp[maxn][maxn];
17 int s[maxn][maxn];
18 int cost[maxn][maxn];
19 int sum[maxn];
20 
21 template<class T>inline void read(T &x){
22     x = 0;bool flag = 0;char ch = getchar();
23     while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
24     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
25     if(flag) x = -x;
26 }
27 
28 template<class T>void putch(const T x){
29     if(x > 9) putch(x / 10);
30     putchar(x % 10 | 48);
31 }
32 
33 template<class T>void put(const T x){
34     if(x < 0) putchar('-'),putch(-x);
35     else putch(x);
36 }
37 
38 void readdata(){
39     read(n);read(p);
40     for(int i = 1;i <= n; ++ i) read(a[i]);
41     sort(a+1,a+n+1);
42 }
43 
44 void work(){
45     for(int i = 2;i <= n; ++ i) sum[i] = sum[i-1]+a[i]-a[i-1];
46     //这里的前缀和求的是各个村庄的距离的前缀和，与村庄的位置无关
47     //所以应该从2开始 
48     for(int i = 2;i <= n; ++ i) sum[i] += sum[i-1];
49     //这里再求一次前缀和，初始化cost的时候会用 
50     
51     //cost是指在[l,r]这个区间里有一处邮局的最小距离和
52     //当然是建在中点划算啦 
53     for(int l = 1;l <= n; ++ l)
54         for(int r = l;r <= n; ++ r){
55             int mid = (l+r)>>1;
56             cost[l][r] = sum[r]-sum[mid]
57                        - (sum[mid]-sum[mid-1])*(r-mid-(mid-l))
58                        - (sum[mid-1]-sum[l-1]); //%%%
59             cost[r][l] = cost[l][r];
60         }
61     
62     memset(dp,0x3f3f3f3f,sizeof(dp));
63     for(int i = 1;i <= n; ++ i)
64         dp[i][1] = cost[1][i];
65     //这里初始化了dp[i][1],就是前i个村庄建1个消防站 
66     for(int j = 2;j <= p; ++ j){
67         s[n+1][j] = n;
68         //避免越界 
69         for(int i = n;i >= 1; -- i){
70             for(int k = s[i][j-1]; k<= s[i+1][j]; ++ k){
71                 if(dp[k][j-1] + cost[k+1][i] < dp[i][j]){
72                     dp[i][j] = dp[k][j-1] + cost[k+1][i];
73                     s[i][j] = k;
74                 }
75             }  
76         }
77     }
78     put(dp[n][p]);
79 }
80 
81 int main(){
82     readdata();
83     work();
84     return 0;
85 }

View Code