cf366C Dima and Salad (dp)

是一个01分数规划的形式，只不过已经帮你二分好了。

把b乘过去，再减回来，找和等于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 }

 

转载于:https://www.cnblogs.com/Ressed/p/9985791.html

总结

以上是生活随笔为你收集整理的cf366C Dima and Salad (dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。