fork(1) download
copy 
  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
comments (?)
stdin
copy 
1
7 3
9 50 20 39 25 41 10
1 2 3 4 5 6 7
stdout
copy 
31
https://ideone.com/dhf4tU
language:
C++ (gcc 8.3)
created:
8 years 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!