又是惨烈的一天
第一题
多重背包。二进制拆分即可。
#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
int n,m,i,j,k,l,a,b;
int d[11][11];
// s: time w: value
int s[10000],w[10000],pn,f[1000000];
int main(){
freopen("medic.in","r",stdin);
freopen("medic.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=0;i<n;++i){
scanf("%d%d",&a,&b);
++d[a][b];
}
for(i=1;i<11;++i){
for(j=1;j<=11;++j){
k=1;
while(d[i][j]){
if(d[i][j]>k){
s[pn]=i*k,w[pn]=j*k,++pn;
d[i][j]-=k;
k<<=1;
}else{
s[pn]=i*d[i][j],w[pn]=j*d[i][j],++pn;
d[i][j]=0;
}
}
}
}
for(i=0;i<pn;++i){
for(j=m;j>=s[i];--j){
f[j]=max(f[j],f[j-s[i]]+w[i]);
}
}
printf("%d\n", f[m]);
return 0;
}
第二题
先将数读入为素因子里2和5分别的个数，然后求出一路乘到底最少的2和5的个数，取其小者。
(DP)
#include <cstdio>
#define min(a,b) ((a)<(b)?(a):(b))
int m,n,i,j,k,f2[2000][2000],f5[2000][2000],fmin[2000][2000],d2[2000][2000],d5[2000][2000],t;
inline int countbit(int n){
t=0;
while(!(k&1)) k>>=1,++t;
return t;
}
inline int countf(int n){
t=0;
while(!(k%5)) k/=5,++t;
return t;
}
int main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=0;i<n;++i){
for(j=0;j<m;++j){
scanf("%d",&k);
d2[i][j]=countbit(k);
d5[i][j]=countf(k);
// printf("(2: %d | 5: %d) ",d2[i][j],d5[i][j]);
if(!i){
f2[i][j]=f2[i][j-1]+d2[i][j];
f5[i][j]=f5[i][j-1]+d5[i][j];
}else if(!j){
f2[i][j]=f2[i-1][j]+d2[i][j];
f5[i][j]=f5[i-1][j]+d5[i][j];
}else{
f2[i][j]=min(f2[i-1][j],f2[i][j-1])+d2[i][j];
f5[i][j]=min(f5[i-1][j],f5[i][j-1])+d5[i][j];
}
}
printf("\n");
}
printf("%d\n",min(f2[n-1][m-1],f5[n-1][m-1]));
return 0;
}
第三题
递推。太懒不写。