正经动态规划题解

#include<bits/stdc++.h>
using namespace std;
    int main(){
    int n,m;
    cin>>n>>m;
    int a[105],b[10004];
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    int dp[10004]={};
    for(int i=1;i<=n;i++){
        dp[i]=b[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i]=max(dp[i],dp[i-a[j]]+b[i]);
        }
    }
    int  ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}