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
| long long helper(vector<vector<long long>>& dp, vector<vector<long long>>& dpp, vector<int>& A, int l, int r) {
if(l == r) return 1e18;
if(dp[l][r] != -1) return dp[l][r];
if(l + 1 == r) {
dpp[l][r] = l;
return dp[l][r] = A[r] - A[l];
}
long long& res = dp[l][r] = 1e18;
long long& cut = dpp[l][r];
for(int i = l + 1; i < r; i++) {
long long now = helper(dp, dpp, A, l, i) + helper(dp, dpp, A, i, r) + A[r] - A[l];
if(now < res) {
cut = i;
res = now;
}
}
return res;
}
void dfs(vector<vector<long long>>& dp, vector<int>& A, vector<int>& res, unordered_set<int>& inc, int l, int r) {
if(l + 1 == r) {
if(!inc.count(A[l])) res.push_back(A[l]);
if(!inc.count(A[r])) res.push_back(A[r]);
} else {
int cut = dp[l][r];
res.push_back(A[cut]);
inc.insert(A[cut]);
dfs(dp,A,res,inc,l,cut);
dfs(dp,A,res,inc,cut,r);
}
}
vector<int> Solution::rodCut(int A, vector<int> &B) {
B.push_back(0);
B.push_back(A);
sort(begin(B), end(B));
int n = B.size();
vector<vector<long long>> dp(n, vector<long long>(n,-1));
vector<vector<long long>> dpp(n, vector<long long>(n,-1));
helper(dp,dpp,B,0,n-1);
vector<int> res;
unordered_set<int> inc {0, B[n - 1]};
dfs(dpp,B,res,inc,0,n-1);
return res;
}
|
