https://www.luogu.com.cn/problem/list?keyword=背包&tag=139&difficulty=7&page=1
[HNOI2007]梦幻岛宝珠
题目描述
解法
多步 (dp) 往往最为致命。
这道题是不可能直接背包的，只有一个条件能用 (aleq10,bleq30) ，这决定了你能不能做出来这题。
有一个原则是把较小的东西放进状态中 (dp) ，上面那个条件提示我们可以按二进制数位考虑，(f[i][j]) 表示对于 (2^i) 的数位用了 (j) 个，那么花费的真实容量是 (2^i imes j) ，第二维的上界是 (10 imes n) 所以这个可以直接 (01) 背包。
然后合并这些数位就可以得到答案，这时候再做一个 (dp) ，设 (g[i][j]) 表示合并了前 (i) 个数位用掉了容量是 (2^i imes j) ，这个状态设计的原则还是放较小的东西 ，这一位用不完的容量可以留给下一位，所以就得到了方程：
那个 (10n) 就是表示这个上界就够用了，(bitm[i-1]) 容量在 (2^{i-1}) 这一位上是否有值，由于最后的答案是 (g[log-1][1]) 只考虑了最大的数位，所以其他的数位是要在 (dp) 过程中补上的（(log) 表示 (m) 的二进制有多少位，它的最高位一定是 (1)）
( t UPD2021/10/26)：可以直接从高位到低位考虑，那么只用留下 (10n) 的容量足够，所以时间复杂度正确。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 1005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,x,lg,f[35][M],g[35][M],pw[35];
void solve()
{
pw[0]=1;lg=0;x=m;
while(x>0) x>>=1,lg++;
for(int i=1;i<=30;i++)
pw[i]=pw[i-1]*2;
for(int i=1;i<=n;i++)
{
int w=read(),v=read();
for(int j=0;j<=30;j++)
if(w%pw[j]==0 && w/pw[j]<=10)
{
int a=w/pw[j];
for(int k=10*n;k>=a;k--)
f[j][k]=max(f[j][k],f[j][k-a]+v);
break;
}
}
for(int j=1;j<=10*n;j++) g[0][j]=f[0][j];
for(int i=1;i<=lg;i++)
{
for(int j=0;j<=10*n;j++)
for(int k=0;k<=j;k++)
g[i][j]=max(g[i][j],f[i][j-k]
+g[i-1][min(10*n,2*k+((m>>i-1)&1))]);
}
printf("%d
",g[lg-1][1]);
}
signed main()
{
while(~scanf("%d %d",&n,&m))
{
if(n==-1 && m==-1) break;
memset(f,0,sizeof f);
memset(g,0,sizeof g);
solve();
}
}
星空
题目描述
解法
看到这种题就直接想到差分了，这样我们就能把区间修改变成单点修改。
关注到题目的关键条件是没点亮的灯泡数量是很少的，我们设 (1) 表示没点亮的灯泡，我们考虑 (1) 对差分数组的影响，让差分数组的长度为 (n+1) ，(b[i]=a[i]oplus a[i-1]) ，那么由于最后一位是 (0) ，变成 (1) 之后一定会变成 (0) ，所以差分数组的 (1) 的个数是偶数，且小于等于 (16)
现在要消去这些 (1) ，由于消去的操作是异或两个位置，那么可以把 (1) 两两消去，发现消去的代价之和距离有关，我们把每种长度拆成 (x) 和 (-x) 然后去做完全背包，就可以算出消去的代价了。
然后由于 (1) 的个数很少搞个状压就行了，如果 (1) 的个数较大的话应该可以写最大权完美匹配。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 40005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,k,m,t,a[M],b[M],c[M],dp[M],f[1<<16];
signed main()
{
n=read();k=read();m=read();
for(int i=1;i<=k;i++)
a[read()]=1;
for(int i=1;i<=n+1;i++)
if(a[i-1]^a[i])
b[++t]=i;
for(int i=1;i<=m;i++)
c[i]=read();
memset(dp,0x3f,sizeof dp);
memset(f,0x3f,sizeof f);
dp[0]=f[0]=0;
for(int i=1;i<=m;i++)
for(int j=c[i];j<=n;j++)
dp[j]=min(dp[j],dp[j-c[i]]+1);
for(int i=1;i<=m;i++)
for(int j=n-c[i];j>=0;j--)
dp[j]=min(dp[j],dp[j+c[i]]+1);
for(int i=1;i<(1<<t);i++)
{
for(int j=0;j<t;j++)
for(int k=j+1;k<t;k++)
if((i&(1<<j)) && (i&(1<<k)))
{
int p=i-(1<<j)-(1<<k);
f[i]=min(f[i],f[p]+dp[b[k+1]-b[j+1]]);
}
}
printf("%d
",f[(1<<t)-1]);
}