E08【模板】背包DP 01背包

#include<bits/stdc++.h>
using namespace std;
int t[110],m[110];
int f[110][1100];
int main()
{
    int T,n;scanf("%d%d",&T,&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&m[i]);
    
    for(int j=0;j<=T;j++) f[0][j]=0;
    for(int i=0;i<=n;i++) f[i][0]=0;
      
    for(int i=1;i<=n;i++)
    {
       for(int j=1;j<=T;j++)
       {
            if( j<t[i])
                f[i][j]=f[i-1][j];
            else
                f[i][j]= max(   f[i-1][j],   f[i-1][j- t[i] ]  +  m[i] );
             
       }
    }
      
    printf("%d\n",f[n][T]);
      
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int m[101],t[101];
int f[1100];
int main()
{
    int n,T;scanf("%d%d",&T,&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&m[i]);
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        for(int j=T;j>=t[i];j--)
        {
            f[j]=max(f[j],f[j-t[i]]+m[i]);
        }
    }
    printf("%d",f[T]);
    return 0;
}