动态规划

#include<bits/stdc++.h>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=1e18;
ll dp[10010];
ll a[10010];
ll b[10010];
int main(){
    ll n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    ll k=-N;
    for(int i=0;i<n;i++){
        dp[i]=k;
    }
    dp[0]=0;
    ll ans=-N;
    for(int x=0;x<n;x++){
        for(int i=0;i<m;i++){
            ll nx=x+a[i];
            if(nx>=n){
                ans=max(ans,dp[x]+b[x]);
            }else{
                dp[nx]=max(dp[nx],dp[x]+b[x]);
            }
        }
    }
    cout<<ans;
    return 0;
}