Luogu-p1107 [bjwc2008] Lei Tao's kitten

Lei Tao is very loving , In his dorm , Keeping a kitten rescued from injury ( Of course , Such behavior is against the regulations of student dormitory management ). Under his care , The kitten soon recovered , And more lively and lovely .

But one day , Lei Tao returns to his bedroom after class , But I found the kitten missing ！ After a search , I found that she was lying on the balcony in a daze at the persimmon tree outside the window …

On the campus of Peking University , There are many persimmon trees , In front of Lei Tao's dormitory , There is N Tree . And this N The height of each persimmon tree is H. The cold of winter gradually enveloped the earth , The leaves on the tree are gradually disappearing , There are only yellow persimmons left , It looks very pleasant . Lei Tao's kitten happens to love persimmons very much , Looking at the persimmons on the tree outside the window , She is very greedy , So I decided to use my agile jumping ability to jump into a tree and eat persimmons .

The kitten can jump from the balcony of the dormitory to the top of any persimmon tree outside the window . after , She can jump down the persimmon tree at her current position every time 1
Unit distance . Of course , The kitten's ability is far more than that , She can also jump between trees . Every time she can jump from the current tree to any other one , In the process , Her height will drop
Delta Unit distance . Every moment , As long as there are persimmons in her position , She can eat . Whole “ Eat persimmons ” Until the kitten falls to the ground .

Lei Tao investigated the growth of persimmons on all persimmon trees . He wants to know , The kitten set out from the balcony , How many persimmons can you eat at most ？ He knows that writing a program can easily solve this problem , But now he is lazy to write any code . therefore , Now your task is to help Lei Tao write such a program .

Original link
Really excited , Before doing questions, you will get stuck, and then you can understand after reading the solution , This is the first dynamic programming problem I have worked out by myself , It can only be made now. It seems that there is a la carte ..., That label says greed , I read the question for a while , I don't know , How greedy , So try dp To do it , I didn't expect to pass . It's right to brush questions
for the first time , I used a triple loop , The third is from the i Jump from one tree to another and get the most persimmons . then 30 Minute timeout
Code ：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4005;
int dp[N][N];
int main()
{
    
    ios::sync_with_stdio(false);
    int n,h,d;
    memset(dp,0,sizeof(dp));
    cin>>n>>h>>d;
    int t,x;
    for(int i=1;i<=n;i++){
    
        cin>>t;
        for(int j=1;j<=t;j++){
    
            cin>>x;
            dp[i][x]++;
        }
    }
    for(int j=h;j>=1;j--)
        for(int i=1;i<=n;i++){
    
            int temp = dp[i][j];
            for(int k=1;k<=n;k++){
    
                if(i!=k)
                    dp[i][j] = max(dp[i][j+1],dp[k][j+d]);
            }
            dp[i][j]+=temp;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
    
            ans = max(ans,dp[i][1]);
        }
        cout<<ans;
    return 0;
}

Although it timed out , But I believe it dp The correctness of the
So I use an array to store the height j The maximum number of persimmons per hour , It becomes a double cycle , It's over

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4005;
int dp[N][N];
int a[N];
int main()
{
    
    ios::sync_with_stdio(false);
    int n,h,d;
    memset(dp,0,sizeof(dp));
    cin>>n>>h>>d;
    int t,x;
    for(int i=1;i<=n;i++){
    
        cin>>t;
        for(int j=1;j<=t;j++){
    
            cin>>x;
            dp[i][x]++;
        }
    }
    for(int j=h;j>=1;j--)
        for(int i=1;i<=n;i++){
    
            dp[i][j] = max(dp[i][j+1],a[j+d])+dp[i][j];
            a[j] = max(a[j],dp[i][j]);
        }
        int ans=0;
        for(int i=1;i<=n;i++){
    
            ans = max(ans,dp[i][1]);
        }
        cout<<ans;
    return 0;
}