A.饭票
- 传统题 1000ms 256MiB
Description
XX中的食堂在使用饭卡之前使用饭票 饭票并不向饭卡一样方便。比如你有1张5饭票和3张1饭票，则你无法付4的饭费。 某天小x去食堂吃饭，手里有n种饭票，面值分别为A1～An,数量分别为C1～Cn 请你计算小x的饭票能组成多少在[1,m]区间内的面值。
Format
Input
第一行2个数n m，用空格隔开。 第二行前n个数，分别为A1..An 第二行后n个数，分别为C1..Cn 1 ≤ n ≤ 100 1 ≤ Ai ≤ m ≤ 1 ≤ Ci ≤ 1000
Output
一个数，即问题的答案
Samples
输入数据 1
输出数据 1
Limitation
1s, 1024KiB for each test case.
一言——DP+二进制拆分
keys:
状态表示：bool num[i]：i是否能被凑出
状态转移：num[j]->num[j+sum[i]]
tips:
1.总和最大100**1000，开long long
2.二进制拆分：如把10拆分成1，2，4，3 四个数字，则它们可以凑出1-10的任意数 字，从而优化
B.Cow Frisbee Team 奶牛沙盘队
- 传统题 1000ms 256MiB
Description
农夫顿因开始玩飞盘之后，约翰也打算让奶牛们享受飞盘的乐趣．他要组建一只奶牛飞盘队．他的N(1≤N≤2000) 只奶牛，每只部有一个飞盘水准指数Ri(1≤Ri≤)．约翰要选出1只或多于1只奶牛来参加他的飞盘队．由于 约翰的幸运数字是F(1≤F≤1000)，他希望所有奶牛的飞盘水准指数之和是幸运数字的倍数．帮约翰算算一共有多少种组队方式．
Format
Input
第1行输入N和F，之后N行输入Ri．
Output
组队方式数模10^8取余的结果．
Samples
输入数据 1
输出数据 1
//组队方式有(2，3)，(3，4)，(1，2，4)共三种
DP+取（驱）模（魔）操作
keys:
状态表示：d[i][j]：第i层中若干数字，对f取模为j的方案数
状态转移：d[i][j]->d[i+1][j]
d[i][j]->d[i+1][(j+num[i+1)%f]
tips：
1.取模操作可以把如和为f+1,2f+1,3f+1…等情况总结为一种嘞
2.滚动数组:二维->一维
从num[1][…]更新到num[0][…],再从num[0][…]更新到num[1][…],循环往复
更新机制如下图
所以呢，每次清空num[1-i%2]就可以辣
C.避开水坑
- 传统题 1000ms 256MiB
Description
给定一条长为N的路，每一单位的路段可能为 X （水坑）或 . （空地）
要求经过最少的水坑到达N这里，每一步可以走1、2、3单位长的距离。
Format
Input
第一行给出N
第二行给出一个长度为N的字符串
N<=100
Output
如题
Samples
输入数据 1
输出数据 1
模（ea）板（sy）DP捏
D.狗狗吃骨头
- 传统题 1000ms 256MiB
Description
一天，主人买来N个BONE(1 <= N <= 150,000)，从左向右排成一排. 狗狗想把所有的BONE全吃了，但这似乎不太可能的.主人说：狗狗，你做为我的宠物,应该要足够的聪明伶俐，睿智过人，玉树临风.我来考一下你.这里每一个BONE都有一个分数K(1<=K<=500)。你从第一个BONE开始.对于每个BONE，你可选也可不选。选择多少个也随便你但你必须从第一个开始选，从左选到右。当你选好BONE后。我会将第一个BONE的分值乘上一个1,第二个则乘上一个-1第三个又是一个1,第四个又是一个-1.然后再加起来。我希望总分值最大。你应该如何选呢
Format
Input
第一行给出一个数字N，代表有多少块Bone. 下面N行，每行一个数字，代表每块Bone的权值。
Output
如题
Samples
输入数据 1
输出数据 1
输入数据 2
输出数据 2
Hint
取7 1 8 3 6，得到+7-1+8-3+6=17。
一丢丢难的DP
状Idea激活2023.3.5态表示:d[i][j]，j=0 or 1:第i层，下一个数字为正或负，当前获得的最大值
状态转移:d[i][0]->d[i+1][0],d[iIdea激活2023.3.5+1][1]+num[i+1]
d[i][1]->d[i+1][1],d[i+1][0]-num[i+1]
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/135067.html
