3372: 【USACO2009MAR】奶牛飞盘队

Memory Limit:256 MB Time Limit:5.000 S
Judge Style:Text Compare Creator:
Submit:61 Solved:26

Description

Sample Input Copy

4 5
1
2
8
2

Sample Output Copy

3

HINT

思路:::
比较像01背包;我们可以定义一个二维dp[i][j];表示前i头牛所选和为j(mod F)组合数;然后就是建立转移方程,对于每一头牛我们有两种操作
1):不选择该头牛,那么dp[i][j]=dp[i-1][j];
2): 选择该头牛,那我们就应该从前i-1头牛中找到所选和为(j-ma[i])的组合数
综上 转移方程::dp[i]j]+=dp[i-1][j]+dp[i-1][(j-ma[i])]
但需要注意一下(j-ma[i])可能为负的,(j-ma[i]+F)%F就可以变成正数了;
可别忘了初始化:
dp[i][ma[i]]=1;