题解 P2946 【[USACO09MAR]Cow Frisbee Team S】

· · 题解

一、看题

很明显，这是一道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;
}

四、请求

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