BZOJ 3400: [Usaco2009 Mar]Cow Frisbee Team 奶牛沙盘队 动态规划
2024-10-06 15:54:23
3400: [Usaco2009 Mar]Cow Frisbee Team 奶牛沙盘队
题目连接:
http://www.lydsy.com/JudgeOnline/problem.php?id=3400
Description
农夫顿因开始玩飞盘之后,约翰也打算让奶牛们享受飞盘的乐趣.他要组建一只奶牛飞盘
队.他的N(1≤N≤2000)只奶牛,每只部有一个飞盘水准指数Ri(1≤Ri≤100000).约翰要选出1只或多于1只奶牛来参加他的飞盘队.由于约翰的幸运数字是F(1≤F≤1000),他希望所有奶牛的飞盘水准指数之和是幸运数字的倍数.
帮约翰算算一共有多少种组队方式.
Input
第1行输入N和F,之后N行输入Ri.
Output
组队方式数模10^8取余的结果.
Sample Input
4 5
1
2
8
2
Sample Output
3
Hint
题意
有3000只羊,每只羊都有自己的能力值。
问你有多少种选择方案,可以使得羊的能力值之和,是约翰能力值的倍数。
题解:
dp
dp[i][j]表示前i只绵羊,当前mod约翰能力值倍数的为j的方案数。
然后暴力转移
代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e8;
int dp[2][1005];
int now=1,pre=0,n,f;
int main()
{
scanf("%d%d",&n,&f);
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
swap(now,pre);
memset(dp[now],0,sizeof(dp[now]));
dp[now][x%f]++;
for(int j=0;j<f;j++)
{
dp[now][j]=(dp[now][j]+dp[pre][j])%mod;
dp[now][(j+x)%f]=(dp[now][(j+x)%f]+dp[pre][j])%mod;
}
}
printf("%d\n",dp[now][0]);
}
最新文章
- tyvj1089 smrtfun
- HTML5游戏开发引擎,初识CreateJS
- linux下安装zookeeper(单机版)
- 边工作边刷题:70天一遍leetcode: day 86
- Android之指南针(电子罗盘)学习
- jQuery validate运作流程以及重复提示错误问题
- 简述sprintf、fprintf和printf函数的区别
- linux下64位汇编的系统调用(5)
- Django学习(一)连接mysql
- 转载>;>;C# Invoke和BeginInvoke区别和使用场景
- 给新手学习Java的建议
- python http请求及多线程应用
- 通过IOCTL_ATA_PASS_THROUGH访问ATA设备接口
- Ambertools15安装(详细)
- 【题解】 [ZJOI2009]假期的宿舍 (二分图匹配)
- A Dog's Way Home插曲列表
- KVM虚拟机IO处理过程(二) ----QEMU/KVM I/O 处理过程
- 第3章—高级装配—条件化的Bean
- python开发_python中for循环操作
- 【CodeForces - 235C】Cyclical Quest 【后缀自动机】
热门文章
- 自定义泛型_无多态_通配符无泛型数组_jdk7泛型使用
- [iOS]图片高清度太高, 导致内存过大Crash
- AngularJs -- 内置指令
- 第9月第30天 MVP
- bellman-ford算法(判断有没有负环)
- 洛谷 P3749: LOJ 2146: [SHOI2017]寿司餐厅
- 【Python】使用Python将Shellcode转换成汇编
- Nagios配置文件nagios.cfg详解
- Archlinux系统配置学习笔记(一)
- 【PAT】1032 Sharing (25)(25 分)