梦幻岛宝珠
首先值的说明的是这道题在牛客上过了，但在洛谷上没有过（一半TLE），可能洛谷的数据比较叼
- 所以可以将vector去掉，简化数据存储方式，减少不必要的存储方式
- make the upper limit of j more accurate and also smaller by sumw
至于题目的思路，这道题暗示（明示）的很明确了，一是利用2^i 分离解决，二是利用这个数据整合出最终答案，这个比较难：
首先，对于第二部分（g）肯定是要将前i组整合在一起，那么就需要考虑j的意义，j既要能够利用f(i,j)--> j*2^i , 又要能够逐渐趋近于真正的上限maxw，那么别人的思路j*2^i+maxw&(2^u-1)就十分巧妙，然后1*2^len+w&(2^len-1)就是真正的上限，那么值得我学习的就是maxw&(2^len-1)这种得到低len位的方式，以及能够逐渐趋近于真实值的思想，还有就是将数永远看做二进制的形式就能启发思维，甚至简化复杂度
另外，在g的过程中，k的使用就有种暴力的感觉，因为我们很难精确化k ， 这时候就要分析复杂度，看是否需要和可能使用暴力
最后，这个题虽然是暗示，其实以后遇到数据量过大的也可以考虑使用这种类似与ST表的思想或者分块的思想来通过预处理降低时间复杂度
the code before optimizing:
//https://ac.nowcoder.com/acm/problem/20058
#include
#include
#include
#include
#define LOCAL
using namespace std;
const int maxn=101;
int w[maxn]; //save the a in a*2^b of id (1~n)
int v[maxn]; //save the value of id
int f[31][1010]; // for the group of 2^i, we deal with it by 01 backpack
int g[31][1010]; // for the i group, we do 01pack , and j--> j*2^i + maxw&(2^i-1)
vector grp[31];//save the id which has the same b in a*2^b
int read(){
int s=0,f=1,c=getchar();
while(c<'0' || c>'9') { if (c=='-') f=-1;c=getchar();}
while(c>='0' && c<='9') {s=s*10+c-'0';c=getchar();}
return f*s;
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
int n=read(),maxw=read();
int len=31;
while(maxw<=(1<<(--len)));
// cout<>=1;cont++;} the following code is better
while(wgt%(1<<(--cont)));
grp[cont].push_back(i);
w[i]=wgt/(1<=w[grp[b][i]];--j)
f[b][j]=max(f[b][j],f[b][j-w[grp[b][i]]]+v[grp[b][i]]);
// cout<>(b-1))&1))]);
printf("%d\n",g[len][1]);
n=read();maxw=read();
// tmpw=maxw;
// len=0;
// while(tmpw>1) {tmpw>>=1;len++;}
len=31;
while(maxw<=(1<<(--len)));
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
memset(w,0,sizeof(w));
memset(v,0,sizeof(v));
for (int i=0;i<31;++i) grp[i].clear();
}
return 0;
}
the optimized code :
//https://ac.nowcoder.com/acm/problem/20058
#include
#include
#include
#include
#define LOCAL
using namespace std;
const int maxn=101;
int sumw[31];
int w[31][maxn];
int v[31][maxn]; //save the value of id
int f[31][1010]; // for the group of 2^i, we deal with it by 01 backpack
int g[31][1010]; // for the i group, we do 01pack , and j--> j*2^i + maxw&(2^i-1)
int num[31];
int read(){
int s=0,f=1,c=getchar();
while(c<'0' || c>'9') { if (c=='-') f=-1;c=getchar();}
while(c>='0' && c<='9') {s=s*10+c-'0';c=getchar();}
return f*s;
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
int n=read(),maxw=read();
int len=31;
while(maxw<=(1<<(--len)));
while(n!=-1){
for (int i=1;i<=n;++i){
int wgt=read();
int cont=31;
while(wgt%(1<<(--cont)));
// sumw[cont]+=(w[cont][++num[cont]]=wgt/(1<=w[b][i];--j)
for (int j=sumw[b];j>=w[b][i];--j)
f[b][j]=max(f[b][j],f[b][j-w[b][i]]+v[b][i]);
// for (int i=0;i<=10*num[0];++i) g[0][i]=f[0][i];
for (int i=0;i<=sumw[0];++i) g[0][i]=f[0][i];
for (int b=1;b<=len;++b){
sumw[b]+=(sumw[b-1]+1)>>1; // pay attention to the change of /2
// for (int j=0;j<=10*n;++j)
int tmp=((maxw>>(b-1))&1);
for (int j=sumw[b];j>=0;--j)
for (int k=0;k<=j;++k)
g[b][j]=max(g[b][j],f[b][j-k]+g[b-1][min(sumw[b-1],2*k|tmp)]); // even number + 1/0 = even number | 1/0
}
// for (int b=1;b<=len;++b)
// for (int j=0;j<=10*n;++j)
// for (int k=0;k<=j;++k)
// g[b][j]=max(g[b][j],f[b][j-k]+g[b-1][min(10*n,2*k+((maxw>>(b-1))&1))]);
printf("%d\n",g[len][1]);
n=read();maxw=read();
len=31;
while(maxw<=(1<<(--len)));
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
memset(w,0,sizeof(w));
memset(v,0,sizeof(v));
memset(num,0,sizeof(num));
memset(sumw,0,sizeof(sumw));
}
return 0;
}