1 条题解
-
0
#include<bits/stdc++.h> using namespace std; inline int read() { char c=getchar(); int x=0,bj=1; while(c<'0'||c>'9') { if(c=='-') { bj=-1; } c=getchar(); } while(c>='0'&&c<='9') { x=x*10+(c^48); c=getchar(); } return x*bj; } int n,m; int num[31]; int a[31][101]; int w[31][101]; int f[31][1001]; int g[31][1001]; int main() { n=read(),m=read(); while(n+m!=-2) { memset(a,0,sizeof(a)); memset(num,0,sizeof(num)); memset(w,0,sizeof(w)); memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); for(register int i=1;i<=n;i++) { register int x=read(); int cnt=31; while(x%(1<<(--cnt))); a[cnt][++num[cnt]]=x/(1<<cnt); w[cnt][num[cnt]]=read(); } register int cnt=31; while(m<=(1<<(--cnt))); for(register int t=0;t<=cnt;t++) { for(register int i=1;i<=num[t];i++) { for(register int j=10*num[t];j>=a[t][i];j--) { f[t][j]=max(f[t][j],f[t][j-a[t][i]]+w[t][i]); } } } for(register int j=0;j<=10*num[0];j++) { g[0][j]=f[0][j]; }//对0进行初始化 for(register int i=1;i<=cnt;i++) { for(register int j=0;j<=10*n;j++)//因为每位上最多就是10*n,可以节省时间 { for(register int k=0;k<=j;k++) { g[i][j]=max(g[i][j],f[i][j-k]+g[i-1][min(10*n,k*2+((m>>(i-1))&1))]); } } } printf("%d\n",g[cnt][1]); n=read(),m=read(); } return 0; }
- 1
信息
- ID
- 1190
- 时间
- 1000ms
- 内存
- 162MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 29
- 已通过
- 13
- 上传者