是一個(gè)01分?jǐn)?shù)規(guī)劃的形式，只不過(guò)已經(jīng)幫你二分好了。

把b乘過(guò)去，再減回來(lái)，找和等于0的a的最大值就行了

1 #include<bits/stdc++.h> 2 #define pa pair<int,int> 3 #define CLR(a,x) memset(a,x,sizeof(a)) 4 using namespace std; 5 typedef long long ll; 6 const int maxn=105,maxs=2e5+10; 7 8 inline ll rd(){ 9 ll x=0;char c=getchar();int neg=1; 10 while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();} 11 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 12 return x*neg; 13 } 14 15 int N,K,a[maxn],b[maxn]; 16 int f[2][maxs]; 17 18 int main(){ 19 int i,j,k; 20 N=rd(),K=rd(); 21 for(i=1;i<=N;i++) a[i]=rd(); 22 for(i=1;i<=N;i++) b[i]=rd(); 23 int M=1e5; 24 CLR(f,-1); 25 f[0][M]=0; 26 for(i=1;i<=N;i++){ 27 memcpy(f[i&1],f[!(i&1)],sizeof(f[1])); 28 for(j=0;j<=2*M;j++){ 29 int v=a[i]-K*b[i]; 30 if(f[!(i&1)][j]<0) continue; 31 f[i&1][j+v]=max(f[i&1][j+v],f[!(i&1)][j]+a[i]); 32 } 33 } 34 printf("%d\n",f[N&1][M]?f[N&1][M]:-1); 35 return 0; 36 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Ressed/p/9985791.html

總結(jié)

以上是生活随笔為你收集整理的cf366C Dima and Salad (dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。