Dima and Salad CodeForces - 366C背包DP

#include <iostream> #include <cstdio> using namespace std; const int N = 1e4+10; const int inf = 1e8; int dp[N],dp2[N]; int a[110],b[110]; int n,k; int main() { int num; scanf("%d%d",&n,&k); for ( int i=1; i<=n; i++ ) scanf("%d",&a[i]); for ( int i=1; i<=n; i++ ) scanf("%d",&b[i]); for ( int i=1; i<=10000; i++ ) dp[i] = dp2[i] = -inf ; for ( int i=1;i<=n;i++ ) { num = a[i]-b[i]*k; if ( num>=0 ) { for ( int j=10000; j>=num; j-- ) dp[j] = max( dp[j] , dp[j-num]+a[i] ); } else { num = -num; for ( int j=10000; j>=num; j-- ) dp2[j] = max( dp2[j] , dp2[j-num]+a[i] ); } } int ans = -1; for ( int i=10000; i>=0; i-- ) ans = max( ans , dp[i]+dp2[i] ); if ( ans<=0 ) ans = -1 ; cout<<ans<<endl; return 0; }