台州网站平面设计,家装设计学校,提升审美的网站,woocommerce做的网站Description 背景#xff1a; 和久必分#xff0c;分久必和。。。 题目描述#xff1a; 中国历史上上分分和和次数非常多。。通读中国历史的WJMZBMR表示毫无压力。 同时经常搞OI的他把这个变成了一个数学模型。 假设中国的国土总和是不变的。 每个国家都可以用他的国土面积代…Description 背景 和久必分分久必和。。。 题目描述 中国历史上上分分和和次数非常多。。通读中国历史的WJMZBMR表示毫无压力。 同时经常搞OI的他把这个变成了一个数学模型。 假设中国的国土总和是不变的。 每个国家都可以用他的国土面积代替 又两种可能一种是两个国家合并为1个那么新国家的面积为两者之和。 一种是一个国家分裂为2个那么2个新国家的面积之和为原国家的面积。 WJMZBMR现在知道了很遥远的过去中国的状态又知道了中国现在的状态想知道至少要几次操作分裂和合并各算一次操作能让中国从当时状态到达现在的状态。Input 第一行一个数n1表示当时的块数接下来n1个数分别表示各块的面积。 第二行一个数n2表示现在的块接下来n2个数分别表示各块的面积。Output 一行一个数表示最小次数。Sample Input 1 6 3 1 2 3 Sample Output 2 数据范围 对于100%的数据n1,n210每个数50 对于30%的数据n1,n26 代码很短但是我没有想到这个思路 讲出来其实很容易理解我们把两边都分成k堆两边对应的一堆和相等这样我们就只需要做n1n2-k*2次操作就可以了 状压dp即可f[s]表示左边取某些块右边取某些块中间相等次数最多是多少 1 var2 sum,f:array[0..1 shl 21]of longint;3 n1,n2,n:longint;4 5 procedure init;6 var7 i:longint;8 begin9 read(n1);
10 for i:1 to n1 do
11 read(sum[1i1]);
12 read(n2);
13 for i:n11 to n1n2 do
14 begin
15 read(sum[1i1]);
16 sum[1i1]:-sum[1i1];
17 end;
18 n:n1n2;
19 end;
20
21 procedure up(var x:longint;y:longint);
22 begin
23 if xy then x:y;
24 end;
25
26 procedure dp;
27 var
28 i,j,k:longint;
29 begin
30 for i:1 to 1n-1 do
31 begin
32 k:i and (-i);
33 sum[i]:sum[i-k]sum[k];
34 for j:1 to n do
35 if i and (1j1)0 then up(f[i],f[i-1j1]);
36 if sum[i]0 then inc(f[i]);
37 end;
38 write(n-f[1n-1]1);
39 end;
40
41 begin
42 init;
43 dp;
44 end. View Code 转载于:https://www.cnblogs.com/Randolph87/p/3757750.html
