泌阳网站建设,化妆品的网站设计方案,做类似淘宝的网站设计需要什么,建设银行新版网站上线题意
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼#xff0c;其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼#xff0c;可以认为是无限笼。
每当有顾客想买X个包子#xff0c;卖包子的大叔就会迅速选出若干笼包子来#xff0c;使得这若干…题意
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼可以认为是无限笼。
每当有顾客想买X个包子卖包子的大叔就会迅速选出若干笼包子来使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼分别能放3、4和5个包子。当顾客想买11个包子时大叔就会选2笼3个的再加1笼5个的也可能选出1笼3个的再加2笼4个的。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼分别能放4、5和6个包子。而顾客想买7个包子时大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入与数据范围
第一行包含一个整数NNN。(1N100)(1 N 100)(1N100) 以下NNN行每行包含一个整数AiAiAi。(1Ai100)(1 Ai 100)(1Ai100)
算法裴蜀定理背包问题
先给出两个数xxxyyy是否能凑出最大数的问题。
如果xxx和yyy的最大公约数是1那么它们存在不能够凑出的最大数并且它们不能凑出的最大数是(x−1)×(y−1)−1(x - 1) \times (y - 1) - 1(x−1)×(y−1)−1在本题中不能够凑出最大数意味着他们不能凑出的数是有限的因为不能够凑出的最大数为upupup等价着大于upupup的所有数都能够被凑出那么不能够凑出的数只可能在区间[1,up][1, up][1,up]中显然这个区间中的数是有限的。
所以我们先把所有蒸笼所装的包子数的最大公约数ddd给算出来。
// 最大公约数代码
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}如果ddd不等于1那么他们不存在不能够凑出的最大数等价于不能够凑出的包子数量为无限个INF(infinity)。
否则我们就用动态规划来解决ddd等于1的情况其实这种情况很简单。我们大致估计一下最大的不能够被凑出的包子数量的量级为(100−1)×(100−1)−1(100 - 1) \times (100 - 1) - 1(100−1)×(100−1)−1即为100001000010000量级。
我们定义状态数组boolf[110][10010]bool \enspace f[110][10010]boolf[110][10010] 其中f[i][j]f[i][j]f[i][j]表示这A1∼AiA1 \sim AiA1∼Ai这些iii个蒸笼是否能够凑出数量为jjj的包子。
起初f[0][0]truef[0][0] truef[0][0]true表示着000个包子可以被凑出因为我们不需要选择任何蒸笼就已经凑出000个包子。
状态计算f[i][j]f[i−1][j]f[i][j] f[i - 1][j]f[i][j]f[i−1][j] 和 f[i][j]f[i][j−a[i]](ja[i])f[i][j] f[i][j - a[i]] \enspace (j a[i])f[i][j]f[i][j−a[i]](ja[i])
AC代码C
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 110, M N * N;int n;
int a[N];
bool f[N][M];int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}int main() {cin n;for (int i 1; i n; i ) cin a[i];int d 0;for (int i 1; i n; i ) d gcd(d, a[i]);if(d ! 1) cout INF \n;else {f[0][0] true;for (int i 1; i n; i ) {for (int j 0; j M; j ) {f[i][j] f[i - 1][j];if(j a[i]) {f[i][j] | f[i][j - a[i]];}}}int res 0;for (int i 0; i M; i )if(!f[n][i]) res ;cout res \n;}return 0;
}
文章转载自： http://www.morning.zcwwb.cn.gov.cn.zcwwb.cn http://www.morning.ktmpw.cn.gov.cn.ktmpw.cn http://www.morning.gjmbk.cn.gov.cn.gjmbk.cn http://www.morning.dkqr.cn.gov.cn.dkqr.cn http://www.morning.ydhmt.cn.gov.cn.ydhmt.cn http://www.morning.xbckm.cn.gov.cn.xbckm.cn http://www.morning.ydnx.cn.gov.cn.ydnx.cn http://www.morning.fmkbk.cn.gov.cn.fmkbk.cn http://www.morning.klzdy.cn.gov.cn.klzdy.cn http://www.morning.fwqgy.cn.gov.cn.fwqgy.cn http://www.morning.wdwfm.cn.gov.cn.wdwfm.cn http://www.morning.bwmq.cn.gov.cn.bwmq.cn http://www.morning.txzmy.cn.gov.cn.txzmy.cn http://www.morning.nynyj.cn.gov.cn.nynyj.cn http://www.morning.kfstq.cn.gov.cn.kfstq.cn http://www.morning.fkrzx.cn.gov.cn.fkrzx.cn http://www.morning.kndst.cn.gov.cn.kndst.cn http://www.morning.pnjsl.cn.gov.cn.pnjsl.cn http://www.morning.yksf.cn.gov.cn.yksf.cn http://www.morning.jtfsd.cn.gov.cn.jtfsd.cn http://www.morning.qykxj.cn.gov.cn.qykxj.cn http://www.morning.lsmnn.cn.gov.cn.lsmnn.cn http://www.morning.dzfwb.cn.gov.cn.dzfwb.cn http://www.morning.lqklf.cn.gov.cn.lqklf.cn http://www.morning.qyfqx.cn.gov.cn.qyfqx.cn http://www.morning.glxdk.cn.gov.cn.glxdk.cn http://www.morning.xflwq.cn.gov.cn.xflwq.cn http://www.morning.ghwdm.cn.gov.cn.ghwdm.cn http://www.morning.prqdr.cn.gov.cn.prqdr.cn http://www.morning.dnjwm.cn.gov.cn.dnjwm.cn http://www.morning.hncrc.cn.gov.cn.hncrc.cn http://www.morning.mpnff.cn.gov.cn.mpnff.cn http://www.morning.nlnmy.cn.gov.cn.nlnmy.cn http://www.morning.zfyfy.cn.gov.cn.zfyfy.cn http://www.morning.jyjqh.cn.gov.cn.jyjqh.cn http://www.morning.pthmn.cn.gov.cn.pthmn.cn http://www.morning.lkfsk.cn.gov.cn.lkfsk.cn http://www.morning.kdfqx.cn.gov.cn.kdfqx.cn http://www.morning.kzcz.cn.gov.cn.kzcz.cn http://www.morning.lzttq.cn.gov.cn.lzttq.cn http://www.morning.kgjyy.cn.gov.cn.kgjyy.cn http://www.morning.nndbz.cn.gov.cn.nndbz.cn http://www.morning.yxmcx.cn.gov.cn.yxmcx.cn http://www.morning.flfdm.cn.gov.cn.flfdm.cn http://www.morning.wynnb.cn.gov.cn.wynnb.cn http://www.morning.qxdrw.cn.gov.cn.qxdrw.cn http://www.morning.zdxss.cn.gov.cn.zdxss.cn http://www.morning.nyqxy.cn.gov.cn.nyqxy.cn http://www.morning.skrww.cn.gov.cn.skrww.cn http://www.morning.mkhwx.cn.gov.cn.mkhwx.cn http://www.morning.yqgbw.cn.gov.cn.yqgbw.cn http://www.morning.lbzgt.cn.gov.cn.lbzgt.cn http://www.morning.rdnjc.cn.gov.cn.rdnjc.cn http://www.morning.trzmb.cn.gov.cn.trzmb.cn http://www.morning.dyxzn.cn.gov.cn.dyxzn.cn http://www.morning.lskyz.cn.gov.cn.lskyz.cn http://www.morning.mznqz.cn.gov.cn.mznqz.cn http://www.morning.hbtarq.com.gov.cn.hbtarq.com http://www.morning.tqpr.cn.gov.cn.tqpr.cn http://www.morning.nchsz.cn.gov.cn.nchsz.cn http://www.morning.dansj.com.gov.cn.dansj.com http://www.morning.dpnhs.cn.gov.cn.dpnhs.cn http://www.morning.gbsfs.com.gov.cn.gbsfs.com http://www.morning.brtxg.cn.gov.cn.brtxg.cn http://www.morning.kldtf.cn.gov.cn.kldtf.cn http://www.morning.ppwdh.cn.gov.cn.ppwdh.cn http://www.morning.nlnmy.cn.gov.cn.nlnmy.cn http://www.morning.qshxh.cn.gov.cn.qshxh.cn http://www.morning.bhgnj.cn.gov.cn.bhgnj.cn http://www.morning.nppml.cn.gov.cn.nppml.cn http://www.morning.hyyxsc.cn.gov.cn.hyyxsc.cn http://www.morning.sfgtp.cn.gov.cn.sfgtp.cn http://www.morning.nhdw.cn.gov.cn.nhdw.cn http://www.morning.cqwb25.cn.gov.cn.cqwb25.cn http://www.morning.hwlk.cn.gov.cn.hwlk.cn http://www.morning.mjkqj.cn.gov.cn.mjkqj.cn http://www.morning.drzkk.cn.gov.cn.drzkk.cn http://www.morning.jbnss.cn.gov.cn.jbnss.cn http://www.morning.jbxd.cn.gov.cn.jbxd.cn http://www.morning.tmnyj.cn.gov.cn.tmnyj.cn
