UVa 907 - Winterim Backpacking Trip Solution

This question can also be solved using bisection method (binary search all possible values). But I solved it using dynamic programming just for the sake of practice. Note that the bisection method solution will be faster.


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  
int n,K;
vector<int> a,cum;
vector<vector<int> > dp;
//last means rest after index last
int rec(int k,int last){
    // cout<<i<<' '<<k<<' '<<last<<endl;
    if(k==0)
        return cum[n]-cum[last];
    if(dp[last][k]!=-1)
        return dp[last][k];
    int tmp,ans=1e9;
    for(int j=last+1;j<n;j++){
        tmp=max(cum[j]-cum[last],rec(k-1,j));
        ans=min(ans,tmp);
    }
    return dp[last][k]=ans;
}
int main(){
    while(!cin.eof()){
        cin>>n>>K;
        n++;
        a.assign(n+1,0);
        cum.assign(n+1,0);
        dp.assign(n+1,vector<int>(K+1,-1));
        for(int i=1;i<=n;i++)
            cin>>a[i];
        cum[0]=0;
        for(int i=1;i<=n;i++)
            cum[i]=cum[i-1]+a[i];
    //cum[i] is sum of i indexes
        if(K>=n-1)
            cout<<*(max_element(a.begin(),a.end()))<<endl;
        else
            cout<<rec(K,0)<<endl;
        ws(cin);
    }
}