![P2946 [USACO09MAR]Cow Frisbee Team S,第1张](/aiimages/P2946+%5BUSACO09MAR%5DCow+Frisbee+Team+S.png "P2946 [USACO09MAR]Cow Frisbee Team S,第1张")
https://www.luogu.com.cn/problem/P2946
题解:
一道需要进行许多处理的01背包问题
首先由于物品数量有2000多,N*R最高将达到惊人的2×10^8,N*N*R,空间不够用
第一时间想到优化成一维滚动数组
如下
#include
#include
#include
#include
#include
using namespace std;
int n,f;
const int N=2010;
const int MOD=1e8;
const int R=3e7;
int d[R];//前i头牛,体积恰好为N
int v[N];
int V;
int main()
{
//freopen("uva.txt","r",stdin);
d[0]=1;
scanf("%d%d",&n,&f);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
V+=v[i];
}
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=V;j>=v[i];j--)
{
d[j]=d[j]+d[j-v[i]];
d[j]%=MOD;
}
}
for(int i=f;i<=V;i+=f)
{
res+=d[i];
res%=MOD;
}
cout< 一发交上去,只能拿80分,优化成1维滚动数组仍然不能拿到满分.
其实显然,即使优化成1维,d的第二维表示的体积(能力值)依然不会被优化到,N*R也是无法接受的
必须要进行压缩.
赛后看了一下题解,是将体积也进行取模缩小范围,存储v[i]时,v[i]%f
由d[j-v[i]]改成d[(j-v[i]+f)%f]
最初的状态转移方程为d[i][j]=d[i-1][j]+d[i-1][j-v[i]]
而有了取模之后
由于原v[i]的大小关系发生了变化(如10模5变成0,2模5模成2, 10反而在了2前面),这样会导致第i层和第i-1层混淆(也就是一些点提前更新了),而我们01背包每次都要用i-1层的数据.
所以只能改成二维,不过此时dp数组第二维最大大小设为F=1000即可.
原来的d[0][0]=1也改成d[i][v[i]]=1 (v[i]事先已对 f 取模) 就是说取v[i]的方法数为1
后面也需要把d[i][j]=改成d[i][j]+=
AC代码
#include
#include
#include
#include
#include
using namespace std;
int n,f;
const int N=2010;
const int MOD=1e8;
const int R=3e7;
const int F=1010;
int d[N][F];//前i头牛,体积恰好为N
int v[N];
int main()
{
//freopen("uva.txt","r",stdin);
scanf("%d%d",&n,&f);
//d[0][0]=1;d[0][0]=1换到了for循环里面的
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
v[i]%=f;
}
for(int i=1;i<=n;i++)
{
d[i][v[i]]=1;
for(int j=0;j 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）