luogu4677山区建小学题解--区间DP

题目链接

https://www.luogu.org/problemnew/show/P4677

分析

这道题方法跟之前题不一样,我们相当于枚举一个左右端点来线性扩展,同时划分断点进行决策

$f[i][j]$表示在前$i$个村庄中建立$j$个小学的最小距离总和

我们将枚举到第$i$个村庄作为阶段,修了$j$所小学作为状态,通过枚举断点$k$来分割第$j$所小学与前$j-1$所小学

也就是说我们判断$f[k][j-1]$加上将新加入的第$j$座小学建在后面的第$k+1$到第$i$座村庄中作出的贡献（也就是新产生的距离,我们假设$f[k][j-1]$已经是最优的）是否更优,那么怎么这个贡献怎么求呢呢?比较显然当小学建在$[k+1,i]$中点处产生的新距离之和最小.为了快速求我们可以先预处理出来

状态转移

1
2
3
4
5
6
7
8
9
memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(ri i=1;i<=n;i++){//枚举第几座村庄 
        for(ri j=1;j<=min(i,m);j++){//枚举修了多少小学 
            for(ri k=j-1;k<i;k++){//断点,枚举前j-1所小学都建在了[1,k]这个区间村庄内 
                f[i][j]=min(f[i][j],f[k][j-1]+dis[k+1][i]);
            }
        }
    }

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#define ll long long 
#define ri register int
using std::min;
using std::abs;
using std::max;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=505;
const int inf=0x7fffffff;
int f[maxn][maxn],s[maxn][maxn],dis[maxn][maxn];
int n,m,pos[maxn];
/*inline int dis(int l,int r){
    int mid=(l+r)>>1,x=0;
    for(ri i=l;i<=r;i++)x+=abs(pos[i]-pos[mid]);
    return x;
}*/
int main(){
    read(n),read(m);
    for(ri i=2;i<=n;i++){
        read(pos[i]);
        pos[i]+=pos[i-1];
    }
    for(ri i=1;i<=n;i++){
    	for(ri j=i;j<=n;j++){
    		s[i][j]+=s[i][j-1]+pos[j];
        }
    }
    for(ri l=1;l<=n;l++){
        for(ri r=l;r<=n;r++){
            int mid=(l+r)>>1;
            dis[l][r]+=(mid-l)*pos[mid]-s[l][mid-1];
            dis[l][r]+=s[mid+1][r]-(r-mid)*pos[mid];
        }
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(ri i=1;i<=n;i++){//枚举第几座村庄 
        for(ri j=1;j<=min(i,m);j++){//枚举修了多少小学 
            for(ri k=j-1;k<i;k++){//断点,枚举前j-1所小学都建在了[1,k]这个区间村庄内 
                f[i][j]=min(f[i][j],f[k][j-1]+dis[k+1][i]);
            }
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}