Divide and conquer optimization

Блог пользователя mak_0111

Автор mak_0111, история, 7 лет назад, По-английски

I have been trying to understand dp divide and conquer optimization but I am not able to solve spoj NKLEAVES (http://www.spoj.com/problems/NKLEAVES/). How to calculate cost function C[i][j] for a bunch of leaves in O(1) time using appropriate preprocessing?

mak_0111
7 лет назад
4

Комментарии (4)

Написать комментарий?

mak_0111

7 лет назад, # |

Auto comment: topic has been updated by mak_0111 (previous revision, new revision, compare).

→ Ответить

tfg

7 лет назад, # |

← Rev. 4 →

Have some preprocessed arrays like this:

sum[i] = sum from right to left or sum[n] = w[n] and sum[i] = sum[i+1] + w[i]

aux[n] = w[n] and aux[i] = aux[i+1] + sum[i]

then you are able to have something like this: 1*w1 + 2*w2 + 3*w3 + 4*w4 + 5*w5... until the rightmost one. To get some part in the middle do this:

1*w1 + 2*w2 + 3*w3 + 4*w4 + 5*w5... — (1*w4 + 2*w5 + 3*w6...) — 3 * (w4 + w5 + w6...) = 1*w1 + 2*w3 + 3*w3

so C[i][j]=aux[i+1]-aux[j+1]-(j-i)*sum[j+1], this would be the cost to take all the leaves from i to j and stack them on i if I understood the problem right.

→ Ответить

mak_0111

7 лет назад, # ^ |

Thank you. This is exactly what I needed.

→ Ответить

hydra_cody

15 месяцев назад, # |

← Rev. 2 →

Can anyone help debug the code?

Spoiler

void dcn(ll i,ll l,ll r,ll opl,ll opr,vl& psum,vl& ausum,vvl& dp){
  if(l>r)return;

  ll mid=(l+r)/2;
  pl x={INF64,l};
  for(ll j=opl;j<min(mid,opr);j++){ 
    ll sum=dp[i-1][j-1] + ausum[j+1]-ausum[mid+1]-(mid-j)*psum[mid+1];
    // cout<<j<<" ";
    if((sum)<x.fi){
      x.fi=sum;
      x.se=j-1;
    }
  }
  // cout<<i<<" "<<mid<<" "<<x.se<<" "<<endl;
  dp[i][mid]=x.fi;
  dcn(i,l,mid-1,opl,x.se,psum,ausum,dp);
  dcn(i,mid+1,r,x.se,opr,psum,ausum,dp);


}
 
void chal(){
  ll n,k;
  cin>>n>>k;
  vl aa(n+1);
  Fo(i,1,n+1){
    cin>>aa[i];
  }
  vl psum(n+5,0);
  psum[n]=aa[n];
  Fo(i,n-1,-1){
    psum[i]+=(psum[i+1]+aa[i]);
  }
  debug(aa);
  debug(psum);
  vl ausum(n+5,0);
  ausum[n]=aa[n];
  Fo(i,n-1,0){
    ausum[i]=ausum[i+1]+psum[i];
  }
  debug(ausum);
  vvl dp(k+5,vl(n+5));
  Fo(i,1,n+1){
    dp[1][i]=ausum[2]-ausum[i+1]-(i-1)*psum[i+1];
  }
  Fo(i,2,k+1){
    dcn(i,1,n,1,n,psum,ausum,dp);
  }
  debug(dp);
  cout<<dp[k][n]<<endl;

  
  
  

  
  
 

}

→ Ответить