Quantify/code/Quantify.java at master · InnoFang/Quantify · GitHub

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
packagecode;

importjava.io.BufferedInputStream;
importjava.util.*;

/**
 * Created by Inno Fang on 2017/6/3.
 */
publicclassQuantify {

privatestaticfinalintMAXN = 100 + 5;
privatestaticfinalintINF = 0x6ffffff;

privatestaticint[] arr = newint[MAXN]; // 数列
privatestaticint[] prefixSum = newint[MAXN]; // 前缀和
privatestaticint[][] sumOfSquares = newint[MAXN][MAXN]; // 保存所有分块中数的差的平方的和
privatestaticint[][] dp = newint[MAXN][10 + 5]; // 保存每个自分块的最优情况

privatestaticScannerin = newScanner(newBufferedInputStream(System.in));

publicstaticvoidmain(String[] args) {

while (in.hasNextInt()) {
intcas = in.nextInt();
for (inti = 0; i < cas; i++) {

intcount = in.nextInt();
ints = in.nextInt();

/* 初始化数列 */
initArray(count);

/* 将数列排序 */
Arrays.sort(arr, 1, count + 1);

/* 计算并保存前缀和 */
initPrefixSum(count);

/* 计算并保存所有分块中的数的差的平方的和 */
initSumOfSquares(count);

/* 使用动态规划 */
dynamicProgramming(count, s);
 }
 }
in.close();
 }

privatestaticvoidinitArray(intcount) {
/* input number */
arr[0] = 0;
for (inti = 1; i <= count; i++) {
arr[i] = in.nextInt();
 }
 }

privatestaticvoidinitPrefixSum(intcount) {
for (inti = 0; i <= count; i++) {
prefixSum[i] = 0;
 }

for (inti = 1; i <= count; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
 }
 }

privatestaticvoidinitSumOfSquares(intcount) {

for (inti = 1; i <= count; i++) {
for (intj = 1; j <= count; j++) {
sumOfSquares[i][j] = 0;
 }
 }

for (inti = 1; i < count; i++) {
for (intj = i + 1; j <= count; j++) {
intaver = averageOf(i, j);
for (intk = i; k <= j; k++) {
sumOfSquares[i][j] += (arr[k] - aver) * (arr[k] - aver);
 }
 }
 }
 }

privatestaticintaverageOf(intfrom, intto) {
return (int) Math.floor(
 (prefixSum[to] - prefixSum[from - 1]) * 1.0
 / (to - from + 1) + 0.5);
 }

privatestaticvoiddynamicProgramming(intcount, ints) {
for (inti = 0; i <= count; i++) {
for (intj = 0; j <= s; j++) {
dp[i][j] = INF;
 }
 }
dp[0][0] = 0;

for (inti = 1; i <= s; ++i) {
for (intj = 1; j <= count; ++j) {
for (intk = 0; k <= j - 1; ++k) {
dp[j][i] = Math.min(dp[k][i - 1] + sumOfSquares[k + 1][j], dp[j][i]);
 }
 }
 }
System.out.println(dp[count][s]);
 }
}