计算客模拟赛1、小区划分

小区划分

1000ms
262144K

一条街道的两侧各连续坐落着

规则如下：

每个小区只能由同一侧连续的若干座单元楼组成。且两侧都恰有
两侧的小区划分规则应该相同，比如，若左边的房子被分成

这样两边合计一共有

用 $a_i,b_iai,bi 表示左右两边每座楼的人口在同侧所有单元楼总人口中所占的百分比，定义一个小区的相对拥挤程度为其人口百分比之和（左边就是对应 a_iai 的和，右边是对应 b_ibi 的和)。定义这条街道的总拥挤程度为左右两边 KK 对小区的相对拥挤程度之差的绝对值之和。$

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

输入格式

第一行两个整数

第二行 $a_iai。$

第三行 $b_ibi。$

输出格式

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

数据范围与约定

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

对于 $100\%100% 的数据：n le 800,k le 80,k le nn≤800,k≤80,k≤n。$

保证 $a_i=1, sum b_i=1∑ai=1,∑bi=1。$

样例解释

这样相对拥挤程度最大为

样例输入

3 2
0.1 0.75 0.15
0.4 0.3 0.3

样例输出

0.600000

code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 810;
 9 double f[MAXN][85];
10 double a[MAXN],b[MAXN],sum1[MAXN],sum2[MAXN];
11 
12 int main() {
13     int n,m;
14     scanf("%d%d",&n,&m);
15     for (int i=1; i<=n; ++i) scanf("%lf",&a[i]),sum1[i] = sum1[i-1]+a[i];
16     for (int i=1; i<=n; ++i) scanf("%lf",&b[i]),sum2[i] = sum2[i-1]+b[i];
17     
18     for (int i=1; i<=n; ++i) {
19         f[i][1] = abs(sum1[i]-sum2[i]);
20         for (int j=2; j<=m&&j<=i; ++j) {
21             for (int k=j-1; k<i; ++k) {
22                 f[i][j] = max(f[i][j],f[k][j-1]+fabs(sum1[i]-sum1[k]-sum2[i]+sum2[k]));
23             }
24         }
25     }
26     printf("%.6lf",f[n][m]);
27     return 0;
28 }