【01背包】[USACO09MAR] Cow Frisbee Team S
P2946 [USACO09MAR] Cow Frisbee Team S
分析
在常规的01背包问题中，有一个很明显的限制条件，常见的都是给出一个最大体积，然后我们根据这个体积限制条件结合物品个数来设计状态表示
那么这道题中限制条件是什么呢，如何看出这道题是01背包问题？题目中要求总能力必须是F的倍数，这就是限制条件。
如上图，如果我们直接枚举所有可能的能力总和，在时间和空间上都会超。因为这题的奶牛数量范围最大为2000，每头奶牛的能力最大为1e5，乘起来就得到了2e8级别的数字，这还只是j的范围。在f[i][j]中，再加上i的最大数量2000，整个dp数组就来到了4e11级别，想都不用想了。
那么怎么优化呢？这题要求总能力是F的倍数，它并不在乎总能力具体是多少，那么我们只需要枚举 j 到 F-1 的位置就可以了啊，每次计算能力都模F，这样整个 j 的数据范围就落在了 0 ~ 999，如下图。
但是这题有几个细节需要注意：
-
在选第i个奶牛时，要用 j - a[i]%f，而不是用 j - a[i]，因为我们用模运算的基本性质已经将
总能力之和再%f转换成了每头奶牛的能力%f再相加，这样更方便计算状态转移方程 -
状态转移方程的选当前奶牛情况中，j-a[i]%m有可能是负数，那么就面临数组越界访问，以及这个数有没有意义的讨论。实际上这个数是有意义的，根据同余理论，可以加上模数让这个负数补正，它们是等价的，意义也相同，在C++中采用模加模补正。
重中之重就是理解：我们需要的是余数值的等价性，而非具体的正负。
详见：模运算的基本性质中的同余类
那么负数是如何产生的呢，请看下图
-
注意 j 的范围是 0 ~ m（模数）- 1，取不到 m
for(int j=0;j<m;j++) -
f[0][0]初始化为1，f[0][0]本身是有意义的，它表示在0头牛中选出总能力模f后为0的方案数，什么都不选本身就符合条件，所以它的方案数为1。但是最后在取结果的时候，f[0][0]要排除掉，因为奶牛队伍中奶牛数量最少为1
-
最终结果在f[n][0]中，0表示总能力和模f后为0，那么总能力就是f的倍数，符合题意
-
这道题是不能使用一个数组来滚动进行空间优化的，因为j - a[i]在补正后有可能位于i-1行的任意位置，有可能在j的左边或者右边，就不能靠常规的逆序加一维数组来优化了。如果非要空间优化那就只能用两个数组来回倒，但这是这样就增加了时间消耗，所以如果不能使用一个数组来进行空间优化，一般就不要优化了，不然会有超时的风险。
题解
#include<iostream>using namespace std;const int N = 2010, M = 1010, MOD = 1e8; int a[N]; //f[i][j]表示在1~i个奶牛中，选出的奶牛的总能力模m后为j的，总方案数
int f[N][M];
int n,m;int main()
{ cin >> n >> m;for(int i=1;i<=n;i++) cin >> a[i];f[0][0] = 1;for(int i=1;i<=n;i++){for(int j=0;j<m;j++) //j取不到m {f[i][j] = (f[i-1][j] + f[i-1][((j-a[i]%m)%m+m)%m]) % MOD; }} cout << f[n][0] - 1 << endl; //排除f[0][0] 奶牛队伍中奶牛数量>=1 return 0;
}