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;