Hybrid Backpack

1. Scrolling array dp Space optimization

2. Discuss the direct classification of different backpacks

01： Enumerate in reverse order

Completely ： Positive order enumeration

Multiple backpack ： Binary grouping

3.!. Pay attention to input, do not use self addition Write separately ！

#include<bits/stdc++.h>
using namespace std;
int t1,m1,t2,m2;
int dp[100006];
int w[2000005],st[2000006],cc[2000006];
int main()
{
    scanf("%d:%d %d:%d",&t1,&m1,&t2,&m2);
    int tt=(t2-t1)*60+m2-m1;
    int n;
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;++i)
    {
        ++cnt;
        scanf("%d%d%d",&st[cnt],&w[cnt],&cc[cnt]);
        if(cc[cnt]>1)
        {
            int c=1;
            int k=cc[cnt];
            int stt=st[cnt];
            int ww=w[cnt];
            while(k-c>0)
            {
                if(stt*c>tt)
                    break;
                k-=c;
                st[cnt]=stt*c;
                cc[cnt]=1;
                w[cnt++]=ww*c;
                c*=2;
            }
            if(k>0&&stt*k<=tt)
            {
                w[cnt]=ww*k;
                cc[cnt]=1;
                st[cnt++]=stt*k;
                
            }
            cnt--;
        }
    }
    
    for(int i=1;i<=cnt;++i)
    {
        if(cc[i]==1)
        {
            for(int j=tt;j>=st[i];--j)
            {
                dp[j]=max(dp[j],dp[j-st[i]]+w[i]);
            }
        }
        if(cc[i]==0)
        {
            for(int j=st[i];j<=tt;++j)
            {
                dp[j]=max(dp[j],dp[j-st[i]]+w[i]);
            }
        }
        
    }
//     for(int i=1;i<=cnt;++i)
//     {
//         cout<<st[i]<<" "<<w[i]<<" "<<cc[i]<<endl;
//     }
//     cout<<cnt<<endl;
    cout<<dp[tt];
    return 0;
}