1.6049:买书
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。
问小明有多少种买书方案？（每种书可购买多本）
- 输入
- 一个整数 n，代表总共钱数。（0 <= n <= 1000）
- 输出
- 一个整数，代表选择方案种数
- 样例输入
-
样例输入1： 20 样例输入2： 15 样例输入3： 0
- 样例输出
- 样例输出1：
- 2
- 样例输出2：
- 0
- 样例输出3：
- 0
- 代码：
/*一个求：恰好放满的完全背包的方案总数的问题，注意特判n==0就可以了*/ #include<cstdio> #include<iostream> using namespace std; #define N 1001 int n; long long int f[N]; int main() { scanf("%d",&n); int a[5]; a[1]=10;a[2]=20;a[3]=50;a[4]=100; f[0]=1; for(int i=1;i<=4;++i) for(int j=a[i];j<=n;++j) f[j]+=f[j-a[i]]; if(n==0) { printf("0 "); return 0; } cout<<f[n]<<endl; return 0; }
专题二：参数过大的背包问题的转化（带有余数问题的DP）
1.2989:糖果
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天，Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖果总数是K的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。Dzx最多能带走多少糖果呢？
注意：Dzx只能将糖果公司的产品整件带走。 - 输入
- 第一行包含两个整数N(1<=N<=100)和K(1<=K<=100)
以下N行每行1个整数，表示糖果公司该件产品中包含的糖果数目，不超过1000000 - 输出
- 符合要求的最多能达到的糖果总数，如果不能达到K的倍数这一要求，输出0
- 样例输入
-
5 7 1 2 3 4 5
- 样例输出
-
14
- 提示
- Dzx的选择是2+3+4+5=14，这样糖果总数是7的倍数，并且是总数最多的选择。
- 代码及解释;
/*问题分析： 方法一：朴素01背包算法：总重量/作为参数，可以用bool判断，能不能达到某个重量 ， 再用贪心倒叙找7的倍数就可以了，但是时间复杂度是n*10000，会超时间 方法二;把sum这个量由参数变为函数值，选择另一个与k有关的作为参数，那就是余数。 状态转移方程：f[i][j]=max(f[i][j],max(f[i-1][j],f[i-1][(k+j-a[i]%k)%k]+a[i])); f[i][j]表是，前i个物品，%k是j的最大糖果数目， 它包括两种情况：1.不取第i个包，那就是 f[i-1][j]， 2.取第i个包，那么就要判断能转移到f[i][j]的前一种状态是什么, f[i-1][(k+j-a[i]%k)%k], 由题目的意思，假设 f[i][j]是由f[i-1][x]转移过来的，那么j=（x+a[i]%k）%k， 根据这个公式，可以得出x是 （k+j-a[i]%k)%k，括号里加一个k的原因，是为了防止 j-a[i]%k小于0的情况。 初始化： memset(f,-128,sizeof(f)); f[0][0]=0;注意这里区别好糖果是0，就是没取包，可以达到余数是0， 而取包之后达不到的状态赋值为-INF,防止出现某个糖果数，是由不成立的状态转移来的。 f[1][0]=0; f[1][a[1]%k]=a[1]; 最后输出;f[n][0] 就可以了。 */ #define INF 100000*100 #include<cstdio> #include<iostream> using namespace std; #include<cstring> #define N 101 int f[N][N],n,k,a[N]; void input() { scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%d",&a[i]); memset(f,-128,sizeof(f)); f[0][0]=0; f[1][0]=0; f[1][a[1]%k]=a[1]; } void DP() { for(int i=2;i<=n;++i) for(int j=0;j<=k-1;++j) f[i][j]=max(f[i][j],max(f[i-1][j],f[i-1][(k+j-a[i]%k)%k]+a[i])); } int main() { input(); DP(); if(f[n][0]>0) printf("%d ",f[n][0]); else printf("0 "); return 0; }
2.codevs 数字三角形W(与余数有关)
但是数字三角形题目是
数字三角形
要求走到最后mod 100最大
如果把每一层作为状态，这一层mod100如果取最大值对于下一层不一定是最优值，所以DP方程比较难写，n==25，规模不大，可以用深搜的方法
3.NOi 判断整除
3531:判断整除
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
一个给定的正整数序列，在每个数之前都插入+号或-号后计算它们的和。比如序列：1、2、4共有8种可能的序列：
(+1) + (+2) + (+4) = 7
(+1) + (+2) + (-4) = -1
(+1) + (-2) + (+4) = 3
(+1) + (-2) + (-4) = -5
(-1) + (+2) + (+4) = 5
(-1) + (+2) + (-4) = -3
(-1) + (-2) + (+4) = 1
(-1) + (-2) + (-4) = -7
所有结果中至少有一个可被整数k整除，我们则称此正整数序列可被k整除。例如上述序列可以被3、5、7整除，而不能被2、4、6、8……整除。注意：0、-3、-6、-9……都可以认为是3的倍数。 - 输入
- 输入的第一行包含两个数：N（2 < N < 10000）和k(2 < k< 100)，其中N代表一共有N个数，k代表被除数。第二行给出序列中的N个整数，这些整数的取值范围都0到10000之间（可能重复）。
- 输出
- 如果此正整数序列可被k整除，则输出YES，否则输出NO。（注意：都是大写字母）
- 样例输入
-
3 2 1 2 4
- 样例输出
- NO
- 变式题目：注意这个符号是插在两个数字之间还是在数字之前加上符号（codevs 整除）
- 代码：
/*f[i][j]:bool类型数组判断 前i个数到达余数是j的情况能不能达到。 如何处理负数：f[i][j]=f[i][j]||f[i-1][(k+j-a[i]%k)%k]||f[i-1][(j+a[i]%k)%k]， 负数当做正数处理，因为后面的数一起变符号，可以得到相同的状态（也就处理了负数可以整除的情况） */ #include<iostream> using namespace std; #include<cstdio> #include<cmath> #include<cstdlib> #define N 10001 #define K 101 bool f[N][K]; int n,k; int a[N]; void input() { scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%d",&a[i]); f[0][0]=true; for(int i=1;i<=n;++i) for(int j=0;j<=k-1;++j) f[i][j]=f[i][j]||f[i-1][(k+j-a[i]%k)%k]||f[i-1][(j+a[i]%k)%k]; if(f[n][0]) printf("YES "); else printf("NO "); } int main() { input(); return 0; }
专题三：最长公共上升子序列加求输出序列
NOI 2000:最长公共子上升序列
- 总时间限制:
- 10000ms
- 内存限制:
- 65536kB
- 描述
- 给定两个整数序列，写一个程序求它们的最长上升公共子序列。
当以下条件满足的时候，我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM的上升子序列：
存在 1 <= i1 < i2 < . . . < iN <= M ，使得对所有 1 <= j <=N，均有Sj = Aij，且对于所有的1 <= j < N，均有Sj < Sj+1。 - 输入
- 每个序列用两行表示，第一行是长度M(1 <= M <= 500)，第二行是该序列的M个整数Ai (-231 <= Ai < 231 )
- 输出
- 在第一行，输出两个序列的最长上升公共子序列的长度L。在第二行，输出该子序列。如果有不止一个符合条件的子序列，则输出任何一个即可。
- 样例输入
-
5 1 4 2 5 -12 4 -12 1 2 4
- 样例输出
- 2
- 1 4
- 分析：一：状态的定义：
- 对于最长子序列的题目，f[i]，定义的是以i结尾的长度，而不是前i个，为了转移的时候方便处理；对于公共子序列，f[i]是第i个，
- （注意状态转移的时候：定义的状态可能有多种，找出每种的状态转移，证明状态转移的可行性和简便）。
- 所以对于两个序列的做法：定义f[i1][i2]是以a串的第i1个结尾，与b串的前i2个匹配所能形成的最长公共上升子序列
- 二：状态的转移
- 1.如果b串中没有a[i1]，那么f[i1][i2]就是0，
- 2.如果a[i1]==b[i2]，那么f[i1][i2]=max{f（i，i2-1）+1} i为1--i1-1的枚举，因为i1这个数可以跟在之前的所有序列任意一个后面，
- 技巧：对于f[i1]记录一个到当前i1-1的最优子序列，可以减少枚举找最优的时间
- 3.如果a[i1]!=b[i2],那么if（a[i1]>b[i2]）f[i1][i2]不变
- if(a[i1]<b[i2]) {f[i1][i2]不变,max{f[i][i2]}更新，为什么有更新呢？因为这个f数组最终会压成一维数组f[i],
- 表示以a[i]结尾的最长公共上升子序列的长度，所以对于f[i][i2]要更新，下面会说到}。
- 三：分析最终的结果是哪个状态
- 容易看出f[i1][i2]在i1不变的情况下，i2越大，f也就越大，所以最终的结果是从所有的1--i1的f[i][序列b的最后一个数]找出最大值
- 四：求出序列的问题:
- 当a[i1]==b[i2]的时候，对于每个f[i1][i2],从{f（i，i2-1）+1}更新最优值，那么v（i1）=v（i）+a[i1]，来储存最优序列，而不会影响到v
- (注意在DP过程中始终维护者v这个序列)
- 当a[i1]!=b[i2]的时候，v（i1）无变化
- 但是对于其他v（i），要进行更新，具体的看代码
- 五：状态的压缩：
- 因为i1与之前i都有关，所以不能压，但是i2，仅仅用到i2-1，所以可以将i2压掉，那么就有注意循环的顺序，压掉的一层i2作为外层循环，i1作为内层
- 循环，
- （注意：在动态规划中，对于题目有了清晰的思路之后，在翻译思路的过程中，考虑到降维和减少时间复杂度的技巧，例如本题代码中的cur的作用）。
- 代码：
- 代码中的注意：结构体是可以直接赋值的，就是把结构体中的每一项都相应的赋值过去。
#include<iostream> using namespace std; #define N 501 #include<cstdio> #include<cstring> struct Xl{ int len; int ans[N]; }; Xl xl[N],now; int a[N],b[N],lena,lenb; void input() { scanf("%d",&lena); for(int i=1;i<=lena;++i) scanf("%d",&a[i]); scanf("%d",&lenb); for(int i=1;i<=lenb;++i) scanf("%d",&b[i]); } void DP() { for(int i=1;i<=lenb;++i) { now.len=0; memset(now.ans,0,sizeof(now.ans)); for(int j=1;j<=lena;++j) { /*xl[j]的含义：到当前循环的1--i区间以a[j]结尾的最长公共上升子序列的长度*/ if(a[j]<b[i]&&xl[j].len>now.len)/*因为只有a[j]<b[i]，才把now更新，可以保证是上升的*/ { now=xl[j]; } if(a[j]==b[i])/*如果不相等，那么xl[j]还是之前的某个b[i]更新过来的，与当前的b[i]就没有关系了*/ { xl[j]=now;/*始终记录着now的最大值，可以减少最大值的寻找，减少一重循环*/ xl[j].len++; xl[j].ans[xl[j].len]=a[j]; } } } } int main() { input(); DP(); int p=0; int maxx=-N; for(int i=1;i<=lena;++i)/*因为f[i]储存着是a[i]结尾的序列，所以f[lena]不一定是最优值，所以要把所有以a[i]为结尾都循环走一边*/ { if(xl[i].len>maxx) { maxx=xl[i].len; p=i; } } printf("%d ",xl[p].len); for(int i=1;i<=xl[p].len;++i) printf("%d ",xl[p].ans[i]); printf(" "); return 0; }