当前位置: 首页 > news >正文

宁德蕉城住房和城乡建设部网站成都seo整站

宁德蕉城住房和城乡建设部网站,成都seo整站,仪征 做网站,做p2p网站的主页模板题意 小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼,其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼,可以认为是无限笼。 每当有顾客想买X个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干…

题意

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼,其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼,可以认为是无限笼。

每当有顾客想买X个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼,分别能放3、4和5个包子。当顾客想买11个包子时,大叔就会选2笼3个的再加1笼5个的(也可能选出1笼3个的再加2笼4个的)。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼,分别能放4、5和6个包子。而顾客想买7个包子时,大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入与数据范围

第一行包含一个整数NNN(1<=N<=100)(1 <= N <= 100)(1<=N<=100)
以下NNN行每行包含一个整数AiAiAi(1<=Ai<=100)(1 <= Ai <= 100)(1<=Ai<=100)

算法(裴蜀定理,背包问题)

先给出两个数xxxyyy是否能凑出最大数的问题。

  • 如果xxxyyy的最大公约数是1,那么它们存在不能够凑出的最大数,并且它们不能凑出的最大数是:(x−1)×(y−1)−1(x - 1) \times (y - 1) - 1(x1)×(y1)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(1001)×(1001)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 AiA1Ai这些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[i1][j]f[i][j]=f[i][j−a[i]](j>=a[i])f[i][j] = f[i][j - a[i]] \enspace (j >= a[i])f[i][j]=f[i][ja[i]](j>=a[i])

AC代码(C++)

#include <iostream>
#include <cstring>
#include <algorithm>using 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.zhongyajixie.com/news/18184.html

相关文章:

  • dw个人网站设计网络营销专家
  • 网站建设个人职责鄂州seo
  • 搜狐快站建站教程站长工具高清无吗
  • 网站开发之后如何上传源码怎么查看网站的友情链接
  • 网站建设技术解决方案鄞州seo服务
  • sm做任务的网站火爆产品的推广文案
  • 郑州网站关键优化精灵
  • 网站怎么怎么做关键字杭州疫情最新消息
  • 网站建设网站定制360地图怎么添加商户
  • 做企业的网站都要准备什么手续优化方案官网电子版
  • 南通网站建设.汕头seo按天付费
  • 肇东市网站seo首页关键词优化
  • 出国越南做网站8000保底百度推广优化方案
  • 东莞做网站一般多少钱上海seo优化公司
  • 网站 公安局备案 接入单位广州网络运营课程培训班
  • wordpress怎么设计网站排名
  • 吴江企业网站制作六年级下册数学优化设计答案
  • 松江网站制作沈阳网站建设制作公司
  • 做网站的空间微信投放广告多少钱
  • 制造业生产管理系统搜索引擎优化文献
  • 谷歌paypal官网登录入口网站关键词排名优化方法
  • ds115j用wordpress朔州网站seo
  • 网站做整站做优化百度竞价点击神器下载安装
  • 彩票网站建设基本流程河南网站公司
  • 企业做网站费用搜索引擎优化的含义
  • 百度没有收录我的网站吗关键词怎样做优化排名
  • 池州网站制作公域名搜索
  • 亚马逊deal网站怎么做深圳网络推广公司
  • 做网站包括图片设计吗百度官方推广平台
  • 网络规划与设计参考文献seo专业学校