Guest User

Untitled

a guest
May 30th, 2018
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define INF 300000000000
  4. #define EPS 0.000000001
  5. #define f first
  6. #define s second
  7. using namespace std;
  8. ll n;
  9. ll dp[3002][4];
  10. ll srr[3002];
  11. ll crr[3002];
  12.  
  13. ll solve(ll ind, ll x,ll num){
  14.     if(x>=3){
  15.         return 0;
  16.     }
  17.     if(ind>=n){
  18.         return INF;
  19.     }
  20.     // cout<<ind<<" "<<x<<" "<<num<<endl;
  21.     // cout<<"DFD"<<endl;
  22.     if(dp[ind][x]!=-1)
  23.         return dp[ind][x];
  24.     ll A=INF,B=INF;
  25.     if(srr[ind]>num){
  26.         A=solve(ind+1,x+1,srr[ind])+crr[ind];
  27.     }
  28.     B=solve(ind+1,x,num);
  29.     dp[ind][x]=min(A,B);
  30.     // cout<<ind<<" "<<x<<endl;
  31.     // cout<<"ans "<<A<<" "<<B<<" "<<dp[ind][x]<<endl;
  32.     return dp[ind][x];
  33. }
  34. int main(){
  35.     cin>>n;
  36.     for(ll i=0;i<n;i++)
  37.         cin>>srr[i];
  38.     for(ll i=0;i<n;i++)
  39.         cin>>crr[i];
  40.     for(ll i=0;i<3002;i++)
  41.         for(ll j=0;j<4;j++)
  42.             dp[i][j]=-1;
  43.     ll ans=solve(0,0,-1);
  44.     // for(ll i=0;i<n;i++){
  45.     //  for(ll j=0;j<3;j++){
  46.     //      cout<<dp[i][j]<<" ";
  47.     //  }
  48.     //  cout<<endl;
  49.     // }
  50.     if(ans==INF)
  51.         cout<<-1<<endl;
  52.     else
  53.     cout<<ans<<endl;
  54.     return 0;
  55. }
Add Comment
Please, Sign In to add comment