当前位置：网站首页>Array division (backpack)

Array division (backpack)

2022-04-22 05:37:00 【Bzdhxs_ nt】

Ideas

consider $f [i]$ Said to $i$ The maximum number of intervals that can be divided at the end
obviously When $\&\& f[j] != -1$ when
$\in [0,i-1]$

Code

int f[5005]; //  With n The maximum number of intervals that can be divided at the end 
void solve(){
    
    int n;cin>>n;
    vector<int> a(n+1),b(n+1);
    forr(i,1,n) cin>>a[i],a[i] += a[i-1];
    forr(i,1,n) cin>>b[i],b[i] += b[i-1];
    mem(f,-1);
    f[0] = 0;
    forr(i,1,n){
    
        forr(j,0,i-1){
    
            if(a[i] - a[j] >= b[i] - b[j] && f[j] != -1) f[i] = max(f[i],f[j]+1);
        }
    }
    cout << f[n] << endl;
}
signed main()
{
    
    int t;cin>>t;
    while(t--) solve();
    return 0;
}