P1926 little bookboy - question brushing Army (DP backpack (01 backpack) state transition equation)

Background

Mathematics is fire , Light up the physical light ; Physics is light , Illuminate the way of Chemistry ; Chemistry is the way , The pit leading to creatures ; Creatures are pits , Bury rational people . Classical Chinese is fire , Light up the palace lamp of history ; History is a lamp , Illuminate the road of society ; Society is the way , To the pit of philosophy ; Philosophy is a pit , Bury liberal arts students .—— Small A

Title Description

Small A“ Brush problem ” Very rampant , Blatantly “ Brush problem ”. He found it in the little book boy now n Like what he likes “ subject ”, Every time “ topic ” All of them need time , And the teacher assigned m Item job , Each assignment has its required time and score , Teacher regulation k A score above is considered a pass . Small A only r Unit time , He wants to pass more “ Brush problem ”.

Input format

first line ：n m k r. The second line ：n Number , For each “ topic ” His needs time . The third line ：m Number . Indicates the time required for each assignment . In the fourth row ：m Number . Represents the score of each assignment .

Output format

a number , For little A Can brush several questions

I/o sample

Input #1

3 4 20 100
15 20 50
10 15 40 40
5 5 10 15

Output #1

2

explain / Tips

There is no failure

about 100% The data of ,n≤10,m≤10,k≤50,r≤150

dp The method is the maximum value that can be obtained in this state .

（ as for dp I'll try to get it out as soon as possible , Let novices understand dp Method ）

First use dp Find the specified time , Score you can get , Then find the first time that is just greater than or equal to the passing score , Subtract the specified time , You will get enough time to brush your own topics .

#include <iostream>
#include <algorithm>
using namespace std;
int n,m,k,r;
int time1[1000];
int time2[1000];
int score[1000];
int dp[1000];
int lt=0;
int max1=0;
int main()
{
    cin>>n>>m>>k>>r;
    for(int i=1;i<=n;i++)
    {
        cin>>time1[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>time2[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>score[i];
    }
    for(int i=1;i<=m;i++)
    {
        for(int t=r;t>=time2[i];t--)
        {
            dp[t]=max(dp[t],dp[t-time2[i]]+score[i]);
        }
    }
    for(int i=1;i<=r;i++)
    {
        if(dp[i]>=k)
        {
            lt=r-i;
            break;
        }
    }
    sort(time1,time1+n);
    for(int i=1;i<=n;i++)
    {
        lt=lt-time1[i];
        if(lt<0)
        {
            break;
        }
        max1++;

    }
    cout<<max1<<endl;
    return 0;
}