Contest3145 - the 37th game of 2021 freshman individual training match_ A: Prizes

//
 problem  A:  Prize 
 The time limit : 1.000 Sec   Memory limit : 128 MB
 
 Title Description 
 Na Zha, the Third Prince of King li of tota , High skill , He wants to catch up with the Olympic Games , Open a mind   Olympic Games , The prize of the winner is refined “ helium -3” Crystal structure ;
 This substance is abundant on the moon   There is , It is colorless 、 Tasteless helium isotopes , It plays an important role in nuclear fusion research .
 helium -3 Or a kind of   Absolutely clean energy , Because it doesn't have the nature of releasing itself , Therefore, no radioactive waste will be produced . But if from   The crystal will be transported back to earth on the moon ？ Na Zha said ： Use my belly pocket ！
 Of course, his belly pocket is vulnerable to solar wind and other factors   Influence , The carrying capacity cannot exceed k（1<=k<=100000）, Beyond that , The belly pocket won't fly ;
 This k value   Na Zha will tell you , It will also tell you the weight of each crystal .  Your task is to make this belly bag transport more crystals at a time .
 Input 
 There are two lines   The first line has two positive integers n and k, Separated by a space . Express n Crystal , The maximum carrying capacity of the belly pocket is k.  The second line has n No more than one. 10000 The positive integer , respectively n Weight of crystals , Use a space between numbers   Grid separation .
 Output 
 There is only one line , This line has only one positive integer , It means that nazha's belly pocket can be transported back at one time   The maximum crystal weight of .
 The sample input  Copy
5 15 
2 4 4 8 10
 Sample output  Copy
14
 Tips 
[ Data restrictions ]
40％ The data of ： 1<=n<=20
100％ The data of ： 1<=n<=100

//
// dp
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+6;
int a[111],dp[111][MAXN];

int main()
{
    int n,k,i,j;

    while( ~scanf("%d%d",&n,&k) )
    {
        memset( a,0,sizeof( a ) );
        memset( dp,0,sizeof( dp ) );

        for( i=1;i<=n;i++ ) scanf("%d",&a[i]);

        for( i=1;i<=n;i++ )
        {
            for( j=1;j<=k;j++ )
            {
                if( j<a[i] ) dp[i][j]=dp[i-1][j];
                else         dp[i][j]=max( dp[i-1][j],dp[i-1][j-a[i]]+a[i] );
            }
        }
        printf("%d\n",dp[n][k]);
    }
    return 0;
}

//
find:
01  How to solve it with one-dimensional array