Combination of stones (weakened version)
Description of topic
https://www.luogu.com.cn/problem/P1775
with
N
(
N
≤
300
)
N(N \le 300)
N(N≤300) piles of stones are arranged in a row, and the number is
1
,
2
,
3
,
?
?
,
N
1,2,3,\cdots,N
1,2,3,?,N. Each pile of stones has a certain mass
m
i
(
m
i
≤
1000
)
m_i(m_i \le 1000)
mi? (mi?≤1000). now this
N
N
N piles of stones are merged into one pile. Only two adjacent piles can be merged each time, and the cost of merging is the sum of the masses of the two piles of stones. After merging, the stones adjacent to the two piles of stones will be adjacent to the new pile. Due to the different order of selection during merging, the total cost of merging is also different. Try to find a reasonable way to minimize the total cost and output the minimum cost.
Input format
first line, an integer
N
N
N.
second line,
N
N
N integers
m
i
m_i
Mi?.
Output format
The output file is only an integer, which is the minimum cost.
Example #1
Sample input #1
4 2 5 3 1
Sample output #1
22
ideas(
o
(
no
3
)
O(n^3)
O(n3))
State representation: f[i][j] represents the minimum cost of merging from L to R into a pile
State transition equation: f[L][R]=f[L][k] + f[k + 1][R] + s[R]-s[L-1]
State calculation: f[L,R]=min(f[L,R],f[L,k] + f[k + 1,R] + s[R]-s[L-1])
Initialization: f[i,i]=0 and the rest are positive infinity
Target: f[1,n]
Note: s is the prefix and array, k is the split point
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 310;
int f[N][N]; //Minimum cost required to combine i and j
int a[N];
int s[N];
int n;
signed main() {<!-- -->
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= n; i ++ ) {<!-- -->
f[i][i] = 0;
s[i] = s[i - 1] + a[i];
}
for (int len = 2; len <= n; len ++ ) {<!-- -->
for (int l = 1; l + len - 1 <= n; l + + ) {<!-- -->
int r = l + len - 1;
for (int k = l; k < r; k ++ ) {<!-- -->
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}
[NOI1995] Stone Merge – Ring
Description of topic
https://www.luogu.com.cn/problem/P1880
Arranged around a circular playground
N
N
There are N piles of stones, now we need to combine the stones into a pile in an orderly manner, and it is stipulated that only adjacent ones can be selected each time
2
2
The 2 piles are merged into a new pile, and the number of stones in the new pile is recorded as the score of the merger.
Try to devise an algorithm to calculate the
N
N
N piles of stones are merged into
1
1
Minimum and maximum score for 1 stack.
Input format
the first of the data
1
1
1 row is a positive integer
N
N
N, means there is
N
N
N piles of stones.
No.
2
2
2 rows have
N
N
N integers, the
i
i
i integers
a
i
a_i
ai? means the first
i
i
i is the number of stones in the pile.
Output format
output total
2
2
line 2, line
1
1
1 row minimum score, No.
2
2
2 lines for the maximum score.
Example #1
Sample input #1
4 4 5 9 4
Sample output #1
43 54
Hint
1
≤
N
≤
100
1\leq N\leq 100
1≤N≤100,
0
≤
a
i
≤
20
0\leq a_i\leq 20
0≤ai?≤20.
Thoughts
Dynamic programming:
State representation: f[l][r] indicates that the size of the currently merged stone pile is len, and the left end point of the stone pile is l , the right endpoint is max/min of the scheme of r
Encountered a circular problem:
You can disassemble the ring and extend the chain twice to form 2n heaps, where i and i + n are the same two heaps.
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 410;
int a[N], s[N];
int f[N][N], g[N][N];
int n;
signed main() {<!-- -->
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
memset(f, 0x3f, sizeof f), memset(g, -0x3f, sizeof g);
cin >> n;
for (int i = 1; i <= n; i ++ ) {<!-- -->
cin >> a[i];
a[i + n] = a[i];
}
for (int i = 1; i <= 2 * n; i ++ ) {<!-- -->
s[i] = s[i - 1] + a[i];
g[i][i] = 0, f[i][i] = 0;
}
for (int len = 2; len <= n; len ++ ) {<!-- -->
for (int l = 1; l + len - 1 <= 2 * n; l + + ) {<!-- -->
int r = l + len - 1;
for (int k = l; k < r; k ++ ) {<!-- -->
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
}
int mi = INT_MAX, mx = -INT_MAX;
for (int i = 1; i <= n; i ++ ) {<!-- -->
mi = min(mi, f[i][i + n - 1]);
mx = max(mx, g[i][i + n - 1]);
}
cout << mi << "\\
" << mx << endl;
return 0;
}
[NOIP2006 Improvement Group] Energy Necklace
Description of topic
https://www.luogu.com.cn/problem/P1063
On the planet Mars, every Mars person wears a string of energy necklaces. on the necklace
N
N
N energy beads. An energy bead is a bead with a head mark and a tail mark, and these marks correspond to a certain positive integer. And, for two adjacent beads, the tail mark of the previous bead must be equal to the head mark of the next bead. Because only in this way, through the action of the sucker (the sucker is an organ for Mars people to absorb energy), the two beads can be aggregated into one bead, and at the same time release the energy that can be absorbed by the sucker. If the head of the previous energy bead is marked as
m
m
m, tail marked as
r
r
r, the head of the last energy bead is marked as
r
r
r, tail marked as
no
no
n, the energy released after polymerization is
m
x
r
x
no
m \times r \times n
m×r×n (Mars units), the heads of newly generated beads are marked as
m
m
m, tail marked as
no
no
n.
When needed, the Mars people use a suction cup to clamp two adjacent beads, and get energy through aggregation until there is only one bead left on the necklace. Obviously, the total energy obtained by different aggregation sequences is different. Please design an aggregation sequence to maximize the total energy released by a string of necklaces.
For example: set
N
=
4
N=4
N=4,
4
4
The head marks and tail marks of the 4 beads are
(
2
,
3
)
(
3
,
5
)
(
5
,
10
)
(
10
,
2
)
(2,3)(3,5)(5,10)(10,2)
(2,3)(3,5)(5,10)(10,2). we use the notation
⊕
\oplus
⊕ represents the aggregation operation of two beads,
(
j
⊕
k
)
(j \oplus k)
(j⊕k) means the first
j
,
k
j,k
j,k The energy released by the fusion of the two beads. Then the first
4
4
4,
1
1
1 The energy released after the polymerization of two beads is:
(
4
⊕
1
)
=
10
x
2
x
3
=
60
(4 \oplus 1)=10 \times 2 \times 3=60
(4⊕1)=10×2×3=60.
This string of necklaces can get the total energy released by an aggregation order of the optimal value:
(
(
(
4
⊕
1
)
⊕
2
)
⊕
3
)
=
10
x
2
x
3
+
10
x
3
x
5
+
10
x
5
x
10
=
710
(((4 \oplus 1) \oplus 2) \oplus 3)=10 \times 2 \times 3 + 10 \times 3 \times 5 + 10 \times 5 \times 10= 710
(((4⊕1)⊕2)⊕3)=10×2×3 + 10×3×5 + 10×5×10=710.
Input format
The first line is a positive integer
N
N
N(
4
≤
N
≤
100
4 \le N \le 100
4≤N≤100), indicating the number of beads on the necklace. The second line is
N
N
N positive integers separated by spaces, all numbers not exceeding
1000
1000
1000. No.
i
i
i number is
i
i
Head markers for i beads (
1
≤
i
≤
N
1 \le i \le N
1≤i≤N), when
i
<
N
i As for the order of the beads, you can determine this: place the necklace on the table without crossings, designate the first bead at will, and then order the other beads in a clockwise direction. a positive integer E. E. E( E. ≤ 2.1 x 1 0 9 E\le 2.1 \times 10^9 E≤2.1×109), which is the total energy released by an optimal aggregation sequence. Ring conversion to chain type: copy the array once and convert it into an array of length 2n. The idea is the same as above, here the length needs to be enumerated from 3, up to n + 1, because the first digit can also be mergedOutput format
Example #1
Sample input #1
4
2 3 5 10
Sample output #1
710
Thoughts
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 210;
int n;
int a[N];
int f[N][N];
signed main() {<!-- -->
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
cin >> n;
for (int i = 1; i <= n; i ++ ) {<!-- -->
cin >> a[i];
a[i + n] = a[i];
}
for (int len = 3; len <= n + 1; len ++ ) {<!-- -->
for (int l = 1; l + len - 1 <= 2 * n; l + + ) {<!-- -->
int r = l + len - 1;
for (int k = l + 1; k < r; k ++ ) {<!-- -->
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
}
}
}
int res = 0;
for (int i = 0; i <= n; i ++ ) res = max(res, f[i][i + n]);
cout << res << endl;
return 0;
}