|
下学期学校开DS和算法的课了，年前复习一下自己高中时候做过的一些dp好题
自从退出ACM之后感觉也蛮久没敲了，顺便也练一练码力
不过回归发现bzoj没了，很多题只能敲一敲，不知道能在哪儿评测，也不知道对不对了((
随缘更新，在2月之前应该能更完
bzoj2287
题意：给出n个物品装容量为M的背包，对于每一个物品i，问当i缺失的时候用剩下i-1个物品装满背包的方案数（n，m<=2e3）
首先考虑一个整的01背包，用傻瓜方法得出f[j]为背包体积为j的时候装满背包的方案书。为然后对于单个物品i，定义g[j]为i物品缺失的时候装满j体积的方案数，直接求得这个结果是有些复杂的（因为需要重新做一次背包，如此的时间复杂度自然是1s承受不了的），因此我们选择容斥，用f[j]减去必定选择此物品i的方案数，此状态可以直接由g[j-w[i]]转移过来，最后输出g[m]即可得出结果
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#define eps (1e-6)
#define PI (acos(-1))
using std::cin;using std::cerr;
using std::cout;using std::endl;
const int MOD=10;
const int MAXN=2e3+5;
int f[MAXN],g[MAXN],w[MAXN];
inline int read()
{
bool flag(0);int x(0);char ch;
while(!isdigit(ch=getchar())){(ch=='-')&&(flag=1);}
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());
return flag?-x:x;
}
int main()
{
int n(read()),m(read());
for(int i=1;i<=n;i++)
{
w[i]=read();
}
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=w[i];j--)
{
f[j]=(f[j]+f[j-w[i]])%10;
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(j<w[i])
{
g[j]=f[j];
continue;
}
else g[j]=(f[j]-g[j-w[i]]+10)%10;
}
for(int j=1;j<=m;j++)
{
printf("%d",g[j]);
j==m?puts(""):printf(" ");
}
}
return 0;
}
poj 3093
题意：给出背包容量和物品体积，问有多少种方案可以使得该背包再也无法装下任何一个物品
将物品顺序排列，则答案可以抽象为，针对每个物品，所有比该物品体积小的全部装进背包，统计用比该物品更大的物品来装满背包，使得该物品无法被装入的方案数，最终答案为这些方案数求和
假设选择的比该物品更大的物品和为sum1，小于该物品的和为sum2该物品体积为vi，背包大小为m，则有：
m-sum2-vi < sum1<=m-sum2
求得这个范围内所有sum1的和
顺序排列之后求后缀和，然后倒序背包求出前K大物品装满背包的方案数，最后把所需答案求和即可得出结果
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstring>
#define LL long long
inline int read()
{
bool flag(0);int x(0);char ch;
while(!isdigit(ch=getchar())){(ch=='-')&&(flag=1);}
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());
return flag?-x:x;
}
const int MAXM=1e3+7;
const int MAXN=55;
int v[MAXN],dp[MAXN][MAXM];
LL sum[MAXN];
bool cmp(const int &a,const int &b)
{
return a>b;
}
int main()
{
int T(read());
for(int cas=1;cas<=T;cas++)
{
int ans=0,cnt=1;
memset(v,0,sizeof(v));
memset(dp,0,sizeof(dp));
memset(sum,0,sizeof(sum));
int n(read()),m(read());
for(int i=1;i<=n;i++)
{
v[i]=read();
}
std::sort(v+1,v+n+1,cmp);
if(v[n]>m)
{
printf("%d 0\n",cas);
continue ;
}
for(int i=n;i>=1;i--)
{
sum[i]=sum[i+1]+v[i];
}
for(int i=0;i<=n;i++)
{
dp[i][0]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=m;j++)
{
dp[i][j]=dp[i-1][j]+dp[i-1][j-v[i]];
}
}
for(int i=n;i>=1;i--)
{
for(int j=std::max(m-sum[i+1]-v[i]+1,0ll);m>=sum[i+1]&&j<=m-sum[i+1];j++)
{
ans=ans+dp[i-1][j];
}
}
printf("%d %d\n",cas,ans);
}
return 0;
}
}
bzoj 2794
考虑到询问数量过多，每次全暴力跑背包肯定是遭不住的
条件1的前半句明显是可以靠排序解决的，我们假设离线询问，此时询问的查询随n的增长变成线性关系，我们只考虑对于b的条件进行判断
暴力背包的最大弊端在于状态比较简单，必须在特定的物体中全部跑一次才能得到结果，但由于此问题中我们只需要判断可行性，不需要给出方案/方案数，所以我们可以考虑针对b来进行转移
设f[i]为c[i]和为k的情况下选取集合当中的b[i]最小值的最大值，很显然如果我们能够完成这个状态转移，只要这个值比给定的m+s要大即可
考虑f[i]的转移，很明显对于每一个询问i每次跑一遍容量的背包，单指针加入物品，最后时间复杂度为O(nm+q)
m和m+s也可以形成两个偏序，原理上来说应该也能用CDQ分治来做，不过这里主要写DP做法，就略了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstring>
#define LL long long
inline int read()
{
bool flag(0);int x(0);char ch;
while(!isdigit(ch=getchar())){(ch=='-')&&(flag=1);}
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());
return flag?-x:x;
}
const int MAXM=1e3+7;
const int MAXN=1e6+5;
const int INF=1e9+7;
class obj
{
public:
int a,b,c;
bool operator<(const obj &z)const
{
return a<z.a;
}
}a[MAXN];
class Query
{
public:
int m,k,s,id;
bool operator<(const Query &z)const
{
return m<z.m;
}
}q[MAXN];
int f[MAXN];
int ans[MAXN];
int n,m;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
a[i].c=read(),a[i].a=read(),a[i].b=read();
}
m=read();
for(int i=1;i<=m;++i)
{
q[i].m=read();q[i].k=read();q[i].s=read();
q[i].id=i;
}
std::sort(a+1,a+n+1);
std::sort(q+1,q+m+1);
int idex=1;f[0]=INF;
for(int i=1;i<=m;++i)
{
while(idex<=n&&a[idex].a<=q[i].m)
{
for(int k=100000;k>=a[idex].c;--k)
{
f[k]=std::max(f[k],std::min(f[k-a[idex].c],a[idex].b));
}
idex++;
}
ans[q[i].id]=(f[q[i].k]>(q[i].m+q[i].s));
}
for(int i=1;i<=m;++i) puts(ans[i]?"TAK":"NIE");
return 0;
}
bzoj1190
经典分层背包问题，貌似是高二暑假的时候我在班上讲dp题的时候选过的一道（后来发现一半的队友都写过这题了，xs）
很多人给的方法是状压，不过我感觉和状压没啥关系(
明显直接裸的01包是寄了，这么大的背包是开不下的。
发现vi有很明显的二进制数字特征，所以根据vi来做，对于一个数来说确定a和b就相当于确定了这个数，所以直接根据a/b来定义状态
f[i][j]表示一共选择j*(2^i)的背包容量的最大价值，当i相同的情况下基本是入门转移式，不多赘述
考虑层与层之间的转移，把原容量M化为二进制，然后把M的信息加入背包当中，把上述背包的状态定义改为j*(2^i)+(w&（(1<< i)-1)容量下的最大价值(新条件保证自己装的容量一定和M有关)
每一次把当前的2^i中分一层到2^(i-1)，然后把M的第i位加入即可
第二次（层层之间）的转移方程为
f[i][j]=max(f[i][j],f[i-1][j-k]+f[ i-1][(k<<1)+((w>>i-1)&1)])
预处理将所有V处理为a*2^b形式，其它的按照上述过程就是裸背包
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
namespace stream
{
void print(LL x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
print(x/10);
}
putchar(x%10+'0');
}
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
}
const int MAXN=12;
LL dp[35][1005];
int v[105];
int w[105];
int W;
int n;
int main()
{
while(1)
{
stream::read(n);
stream::read(W);
if(n==-1&&W==-1)
{
break;
}
std::memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
stream::read(w[i]);
stream::read(v[i]);
}
for(int i=1;i<=n;i++)
{
int s=w[i];
int cnt=0;
while(!(s&1))
{
cnt++;
s>>=1;
}
for(int j=1001;j>=s;j--)
{
dp[cnt][j]=std::max(dp[cnt][j],dp[cnt][j-s]+v[i]);
}
}
int top=0;
int m=W;
while(m)
{
m>>=1;
top++;
}
top--;
for(int i=1;i<=top;i++)
{
for(int j=1001;j>=0;j--)
{
for(int k=0;k<=j;k++)
{
dp[i][j]=std::max(dp[i][j], dp[i][j-k]+dp[i-1][std::min(1001,(k<<1)|((W>>i-1)&1))]);
}
}
}
stream::print(dp[top][1]);
std::putchar('\n');
}
return 0;
}
bzoj4472
树形dp+贪心(堆求最大值)
定义f[u]为以u为根节点的子树的最大价值，假设次数为t[u]
非常简单的状态转移，针对每个点的次数限制，考虑每一次跑完一个子树，回到该节点之后都需要浪费一次，所以直接先将子树的dp全部跑完塞进堆里取前t[u]-1个即可，中间注意遇到负数马上break，因为不会增加最大收益
再定义sole[u]表示以u为子树的节点的最大价值方案是否唯一，定义0为唯一，1为不为1，考虑子树到当前根节点的转移过程
可以非常明显的发现，只有三种情况可以使得方案不唯一:
1、u的子节点v中存在不唯一方案，即sole[v]=1
2、存在子节点的dp[v]，因为此时v可选可不选，造成了多个方案
3、存在一个未被选取的子节点和以被选取的子节点价值相同，意味着可以选择其中一个，造成多个方案
一次dfs转移，算上整个堆排序的过程，复杂度为（nlogn）
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
namespace stream
{
void print(LL x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
print(x/10);
}
putchar(x%10+'0');
}
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
}
const int MAXN=12;
LL dp[35][1005];
int v[105];
int w[105];
int W;
int n;
int main()
{
while(1)
{
stream::read(n);
stream::read(W);
if(n==-1&&W==-1)
{
break;
}
std::memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
stream::read(w[i]);
stream::read(v[i]);
}
for(int i=1;i<=n;i++)
{
int s=w[i];
int cnt=0;
while(!(s&1))
{
cnt++;
s>>=1;
}
for(int j=1001;j>=s;j--)
{
dp[cnt][j]=std::max(dp[cnt][j],dp[cnt][j-s]+v[i]);
}
}
int top=0;
int m=W;
while(m)
{
m>>=1;
top++;
}
top--;
for(int i=1;i<=top;i++)
{
for(int j=1001;j>=0;j--)
{
for(int k=0;k<=j;k++)
{
dp[i][j]=std::max(dp[i][j], dp[i][j-k]+dp[i-1][std::min(1001,(k<<1)|((W>>i-1)&1))]);
}
}
}
stream::print(dp[top][1]);
std::putchar('\n');
}
return 0;
}
|