NKOJ 4250 小区划分（dp）

发表于 |
字数统计: 650字 | 阅读时长 ≈ 3min

P4250小区划分

问题描述

一条街道的两侧各连续坐落着 N 座单元楼。现在要为这些单元楼划分居民校区。

规则如下：

每个小区只能由同一侧连续的若干座单元楼组成。且两侧都恰有 K 个小区（每个小区至少有一栋楼）。

两侧的小区划分规则应该相同，比如，若左边的房子被分成 {1,2},{3} 这两个小区，那么右边也应该如此。

这样两边合计一共有 K 对小区。

用 ai,bii​​,b​i​​ 表示左右两边每座楼的人口在同侧所有单元楼总人口中所占的百分比，定义一个小区的相对拥挤程度为其人口百分比之和（左边就是对应 aia_ia​i​​ 的和，右边是对应 bib_ib​i​​ 的和)。定义这条街道的总拥挤程度为左右两边 KKK 对小区的相对拥挤程度之差的绝对值之和。

现在，请你求出可能的最大拥挤程度。

输入格式

第一行两个整数 N 和 k。

第二行 N 个实数，第 i 个数为 ai​i​​。

第三行 N 个实数，第 i 个数位 bi​i​​。

输出格式

一个实数，表示这条街道的最大相对拥挤程度，保留到小数点后六位。

样例输入

3 2
0.1 0.75 0.15
0.4 0.3 0.3

样例输出

0.600000

提示

对于 30%的数据：n≤20。

对于 100% 的数据：n≤800,k≤80。

保证 ∑ai=1,∑b​i​​=1。

令$F[i][j]$表示前$i$座单元楼，划分成$j$个小区的最大拥挤度，那么容易得到
$$
f[i][j]=max(f[k][j−1]+abs((Suma[i]−Suma[k])−(Sumb[i]−Sumb[k])))
$$
复杂度$O(n^2k)$

关键是注意细节，$F[i][1]$在上述式子中会出问题，因此$F[i][0]$必须赋值为$-inf$，而$F[0][0]=0$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 805
using namespace std;
int n,m;
double A[N],B[N],SA[N],SB[N],F[N][100];
int main()
{
	int i,j,k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%lf",&A[i]),SA[i]=SA[i-1]+A[i];
	for(i=1;i<=n;i++)scanf("%lf",&B[i]),SB[i]=SB[i-1]+B[i];
	for(i=0;i<=n;i++)
	for(j=0;j<=m;j++)F[i][j]=-1e9;
	F[0][0]=0;
	for(i=1;i<=n;i++)
	for(j=1;j<=m&&j<=i;j++)
	for(k=0;k<i;k++)F[i][j]=max(F[i][j],F[k][j-1]+fabs(SA[i]-SA[k]-SB[i]+SB[k]));
	printf("%.6lf",F[n][m]);
}