fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4. using namespace std;
  5.  
  6. // 計算 dp(s, t, m)
  7. int dp(vector<vector<vector<int>>>& memo, const vector<int>& sequence, int s, int t, int m) {
  8.     if (m == 0) return 0;
  9.     if (memo[s][t][m] != -1) return memo[s][t][m];
  10.  
  11.     int minCost = numeric_limits<int>::max();
  12.     for (int i = s + 1; i < t; ++i) {
  13.         for (int k = 0; k < m; ++k) {
  14.             if ((i - s) > k && (t - i) > (m - k - 1)) {
  15.                 int cost = dp(memo, sequence, s, i, k) + dp(memo, sequence, i, t, m - k - 1) + (sequence[t - 1] - sequence[s]);
  16.                 minCost = min(minCost, cost);
  17.             }
  18.         }
  19.     }
  20.  
  21.     return memo[s][t][m] = minCost;
  22. }
  23.  
  24. int main() {
  25.     int n;
  26.     cout << "input how many numbers" << endl;
  27.     cin >> n;
  28.     vector<int> sequence(n);
  29.     cout << "input the numbers vector" << endl;
  30.     for (int i = 0; i < n; ++i) {
  31.         cin >> sequence[i]; // 輸入序列
  32.     }
  33. 	cout << "input how many choose" << endl;
  34.     int m;
  35.     cin >> m; // 輸入要選擇的元素個數
  36.  
  37.     // 初始化記憶數組
  38.     vector<vector<vector<int>>> memo(n + 1, vector<vector<int>>(n + 1, vector<int>(m + 1, -1)));
  39.  
  40.     int result = dp(memo, sequence, 0, n, m);
  41.     cout << "Minimum cost: " << result << endl;
  42.  
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
8
5 3 8 10 15 20 25 30
4
stdout 
input how many numbers
input the numbers vector
input how many choose
Minimum cost: 30
https://ideone.com/Q22gOx
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!