fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long LL;
  5.  
  6. const int INF = 0x3f3f3f3f;
  7. const int N = 205;
  8.  
  9. int dis[N][N];
  10. int dp[N][50];
  11. int dd[201][201][201];
  12. int d[N], cost[N], csum[N];
  13. int n, k, cnt, x;
  14. int test_case;
  15. vector<pair< int, int > > v;
  16.  
  17. int cal(int l,int r) {
  18. if(l >= r) return 0;
  19. int mini = INT_MAX;
  20. for(int i = l; i <= r - 1; i++){
  21. int sum = dd[l][r][i] = dd[l][r - 1][i] + abs(v[i].first - v[r].first);
  22. sum += (abs((r - l)) * v[i].second);
  23. mini = min(mini, sum);
  24. }
  25. int temp = csum[r] - csum[l - 1];
  26. temp -= (v[r].first * (r - l + 1));
  27. temp = abs(temp);
  28. dd[l][r][r] = temp;
  29. temp += (abs((r - l)) * v[r].second);
  30. mini = min(temp, mini);
  31. return mini;
  32. }
  33.  
  34. int main() {
  35. int cas=1;
  36. scanf("%d", &test_case);
  37. assert(test_case >= 1 && test_case <= 10);
  38. while(test_case--)
  39. {
  40. v.clear();
  41. scanf("%d %d",&n, &k);
  42. assert(n >= 1 && n <= 200);
  43. assert(k >= 1 && k <= 35);
  44.  
  45. memset(dp, INF, sizeof(dp));
  46. memset(csum, 0, sizeof(csum));
  47. memset(dd, 0, sizeof(dd));
  48.  
  49. for(int i = 1; i <= n; i++) {
  50. scanf("%d",&d[i]);
  51. assert(d[i] >= 1 && d[i] <= 100000);
  52. }
  53.  
  54. v.push_back(make_pair(-1, -1));
  55. for(int i = 1; i <= n; i++){
  56. scanf("%d", &x);
  57. assert(x >= 1 && x <= 100000);
  58. v.push_back(make_pair(d[i], x));
  59. }
  60.  
  61. sort(v.begin(), v.end());
  62.  
  63. csum[0] = 0;
  64. for(int i = 1; i <= n; i++){
  65. csum[i] = csum[i - 1] + v[i].first;
  66. }
  67.  
  68.  
  69. for(int i = 1; i <= n; i++){
  70. for(int j = 1; j <= n; j++){
  71. dis[i][j] = cal(i,j);
  72. }
  73. }
  74.  
  75. for(int i = 1; i <= n; i++){
  76. dp[i][1] = dis[1][i];
  77. }
  78.  
  79. for(int i = 1; i <= n; i++){
  80. for(int j = 2; j <= k; j++){
  81. for(int p = j-1; p < i; p++)
  82. if(dp[p][j - 1] + dis[p + 1][i] < dp[i][j]){
  83. dp[i][j] = dp[p][j - 1] + dis[p + 1][i];
  84. }
  85. }
  86. }
  87. printf("%d\n", dp[n][k]);
  88. }
  89. return 0;
  90. }
  91.  
  92.  
Success #stdin #stdout 0.03s 35392KB
stdin
1
7 3
9 50 20 39 25 41 10
1 2 3 4 5 6 7 
stdout
31