fork download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<utility>
  6. #include<cstring>
  7. #define INF (int)(1e9)
  8. #define pii pair< int , int >
  9. using namespace std;
  10. int a[205],b[205];
  11. vector<pii> v;
  12. int dp[205][205][40][2];
  13. int func(int pos,int capital,int k,int state)
  14. {
  15.     int last=v.size();
  16.     if(pos==last)
  17.     {
  18.         if(k==0)
  19.         {
  20.             return 0;
  21.         }
  22.         else
  23.         {
  24.             return INF;
  25.         }
  26.     }
  27.     if(capital==last)
  28.     {
  29.         return INF;
  30.     }
  31.     if(k<0)
  32.     {
  33.         return INF;
  34.     }
  35.     if(dp[pos][capital][k][state]!=-1)
  36.     {
  37.         return dp[pos][capital][k][state];
  38.     }
  39.  
  40.     int cost;
  41.     if(pos==capital)
  42.     {
  43.         cost=0;
  44.     }
  45.     else
  46.     {
  47.         cost = abs(v[pos].first-v[capital].first) + v[capital].second;
  48.     }
  49.  
  50.     int X = func(pos,capital+1,k,0);
  51.     int Y;
  52.  
  53.     if(state==0)
  54.     {
  55.         Y = cost + func(pos+1,capital,k-1,1);
  56.     }
  57.     else
  58.     {
  59.         Y = cost + func(pos+1,capital,k,1);
  60.     }
  61.  
  62.     int ans = min( X, Y );
  63.  
  64.     dp[pos][capital][k][state]=ans;
  65.     return ans;
  66. }
  67. int main(){
  68.  
  69.     int t;
  70.     cin>>t;
  71.     while(t--)
  72.     {
  73.  
  74.         int n,m;
  75.         cin>>n>>m;
  76.  
  77.         for(int i=1; i<=n; i++)
  78.         {
  79.             cin>>a[i];
  80.         }
  81.  
  82.         for(int i=1; i<=n; i++)
  83.         {
  84.             cin>>b[i];
  85.         }
  86.  
  87.         v.clear();
  88.         for(int i=1; i<=n; i++)
  89.         {
  90.             v.push_back(pii(a[i],b[i]));
  91.         }
  92.  
  93.         sort(v.begin(),v.end());
  94.  
  95.         memset(dp,-1,sizeof(dp));
  96.         int ans=func(0,0,m,0);
  97.         printf("%d\n",ans);
  98.     }
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 16600KB
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/udMiuL
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!