自动搬运

查看原文

来自洛谷，原作者为

	CCF_zkskyer **

搬运于2025-08-24 21:43:43，当前版本为作者最后更新于2020-06-23 21:06:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一、看题

很明显，这是一道USACO的原题，所以我们得先看题面，小心被坑（本蒟蒻就被坑了！！！）

广大群众都看出来这是一道完完全全的01背包，但还是有些不一样，这里不是求能力最大，而是求能整除幸运数F的总能力有几种

二、构思

大部分朋友听到这里后就不会做了，这恰好就中了出题人的下怀，其实啊，我们不妨直接按题目中的条件去试试，没准就过了呢（AC的魔力）

所以，根据题面所说的，可以看出状态转移方程，其实这道题蛮单纯的

状态转移方程如下：

$$f (i,j) = ( ( f (i,j) + f(i-1,j)) \% mod + f (i-1,(j - cow[ i ] + F ) \% F ] ) \% mod $$

即分奶牛参与或不参与两种情况进行讨论

三、AC代码呈现

#include <bits/stdc++.h>

using namespace std;

const int mod=100000000;//这里定义去模的数，尽量用常数 

long long cow[2005],f[2005][2005];//cow[i]指第i头奶牛的能力，f[i][j]是存前i件物品且余数正好为j时的最大值 

int main()
{
        int N,F;
        
	scanf("%d%d",&N,&F);//输入奶牛数量和幸运数 
    
	for (register int i=1;i<=N;i++) //适当的卡 
	{
		scanf("%d",&cow[i]);//输入奶牛能力 
		cow[i]%=F;//这里可以提前取模，减少时间 
	} 
    
	for (register int i=1;i<=N;i++) f[i][cow[i]]=1;//初始化 
	
        for (register int i=1;i<=N;i++)//列举前i件物品 
        {
    	     for (register int j=0;j<=F-1;j++)//列举余数 
             {
        	  f[i][j]=((f[i][j]+f[i-1][j])%mod+f[i-1][(j-cow[i]+F)%F])%mod;//状态转移方程应用 
             }
	}
    
	printf("%d",f[N][0]);//注意这里是到前n件物品且余数正好为0时的最大值 
    
	return 0;
}

四、请求

本人是中学生，第一次发题解，请大家多多支持，留下你们宝贵的赞，顶我！！！