【小米oj】石头收藏家

【小米oj】石头收藏家

经典背包

#define mm(a) memset(a,0,sizeof(a));
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
#define Fopen freopen("1.in","r",stdin); freopen("m.out","w",stdout);
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,b,a) for(ll i=(b);i>=(a);i--)
#include<bits/stdc++.h>
typedef long long ll;
#define PII pair<ll,ll>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=(int)2e6+5;int a[MAXN],v[MAXN],w[MAXN],n,x,dp[MAXN],m;
int main() {scanf("%d",&m);while(~scanf("%d",&x))a[++n]=x;n>>=1;for(int i=1; i<=n; i++)w[i]=a[i],v[i]=a[i+n];for(int i=1;i<=n;i++){for(int j=m;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}int ans=0;for(int i=0;i<=m;i++)ans=max(ans,dp[i]);printf("%dn",ans);return 0;
}

转载于:.html