[洛谷 2946][USACO09MAR]牛飞盘队

题目链接

https://www.luogu.org/problemnew/show/P2946

题解

显然,这是一道DP题。

用\(f[i][j]\)代表选到第\(i\)头奶牛,\( \mod F\)之后余数为\(j\)的方案数。

那么,我们有两种决策:选当前的奶牛和不选。

状态转移方程就可以表示为:\(f[i][j]=f[i][j]+f[i-1][j]+f[i-1][((j-a[i]) \mod F+F) \mod F]\)

#include <stdio.h>
#define MOD 100000000
int f[2005][1005],a[2005];
int main()
{
 int n,F;
 scanf("%d%d",&n,&F);
 for(int i=1;i<=n;i++)
 {
  scanf("%d",&a[i]);
  f[i][a[i]%F]=1;
 }
 for(int i=1;i<=n;i++)
  for(int j=0;j<F;j++)
   f[i][j]+=(f[i-1][j]+f[i-1][((j-a[i])%F+F)%F])%MOD,f[i][j]%=MOD;
 printf("%d",f[n][0]);
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注