P2946 [USACO09MAR]Cow Frisbee Team S

https://www.luogu.com.cn/problem/P2946

题解: 

一道需要进行许多处理的01背包问题

首先由于物品数量有2000多,N*R最高将达到惊人的2×10^8,N*N*R,空间不够用

第一时间想到优化成一维滚动数组

如下

#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<algorithm>
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<<res;return 0;
}

一发交上去,只能拿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<stdio.h>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<algorithm>
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<f;j++){d[i][j]+=d[i-1][j]+d[i-1][(j-v[i]+f)%f];d[i][j]%=MOD;}}cout<<d[n][0];return 0;
}