长沙产品网站建设,设计好看的网页,知名设计公司logo,前程无忧做一年网站多钱D - 摆花 P1077 [NOIP2012 普及组] 摆花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Description
小明的花店新开张#xff0c;为了吸引顾客#xff0c;他想在花店的门口摆上一排花#xff0c;共 m 盆。通过调查顾客的喜好#xff0c;小明列出了顾客最喜欢的 n 种花为了吸引顾客他想在花店的门口摆上一排花共 m 盆。通过调查顾客的喜好小明列出了顾客最喜欢的 n 种花从 1 到 n 标号。为了在门口展出更多种花规定第 i 种花不能超过 ai 盆摆花时同一种花放在一起且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算一共有多少种不同的摆花方案。
Input
第一行包含两个正整数 n 和 m中间用一个空格隔开。
第二行有 n 个整数每两个整数之间用一个空格隔开依次表示 a1,a2,⋯,an。
Output
一个整数表示有多少种方案。注意因为方案数可能很多请输出方案数对 10^67 取模的结果。
Sample 1
InputcopyOutputcopy 2 4
3 22
Hint
【数据范围】
对于 20%20% 数据有 0n≤8,0m≤8,0≤ai≤8。
对于 50%50% 数据有 0n≤20,0m≤20,0≤ai≤20。
对于 100%100% 数据有 0n≤100,0m≤100,0≤ai≤100。
NOIP 2012 普及组 第三题
解析01背包
这道题是一道背包问题这里我们用三重循环来做
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemap
using namespace std;
typedef long long LL;
const int N 100 5;
const int mod 1e6 7;
int n, m;
int arr[N],dp[N][N];int main() {cin n m;for (int i 1; i n; i) {scanf(%d, arr[i]);}for (int i 0; i n; i) {dp[i][0] 1;}for (int i 1; i n; i) {for (int j 1; j m; j) {for (int k 0; k arr[i]; k) {if (j k) {dp[i][j] dp[i - 1][j - k];dp[i][j] % mod;}elsebreak;}}}cout dp[n][m] endl;return 0;
} E - 导弹拦截
P1020 [NOIP1999 普及组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Description
某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段所以只有一套系统因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度计算这套系统最多能拦截多少导弹如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
Input
一行若干个整数中间由空格隔开。
Output
两行每行一个整数第一个数字表示这套系统最多能拦截多少导弹第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
Sample 1
InputcopyOutputcopy 389 207 155 300 299 170 158 65 6
2Hint
对于前 50% 数据NOIP 原题数据满足导弹的个数不超过 10^4 个。该部分数据总分共 100 分。可使用O(n2) 做法通过。 对于后 50%50% 的数据满足导弹的个数不超过 10^5 个。该部分数据总分也为 100 分。请使用 O(nlogn) 做法通过。
对于全部数据满足导弹的高度为正整数且不超过 5×10^4。
此外本题开启 spj每点两问按问给分。 upd 2022.8.24upd 2022.8.24新增加一组 Hack 数据。
解析 dp最长子序列优化Dilworth 定理
这道题分为两个问
问题一求最长子序列这道题数据比较大不能用朴素的的最长子序列算法为超时。
需要用最长子序列的优化版算法(23条消息) dp最长上升子序列升级版_开朗孔乙己的博客-CSDN博客
问题二问题二实际上是考察Dilworth 定理
对于有限偏序集Finite Partial Order Set其最小链划分Minimum Chain Partition的链的长度等于其最大反链Maximum Antichain的大小。
这个定理告诉我们对于有限的偏序集可以将其划分成若干条链每条链上的元素都满足偏序关系而且这个划分的链的条数等于其中最大的反链的大小反链是指其中没有元素之间有偏序关系的子集。
换句话说偏序集中的任意一个最长的全序子集链都可以在不交集的前提下与其它链组成一个划分而且这个划分中没有两个元素之间有偏序关系的子集的大小即反链的大小就是最小的划分链的数目。
在这道题里就是最长非升子序列的最小个数等于最长上升子序列的长度
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemap
using namespace std;
typedef long long LL;
const int N 1e5 5;
int arr[N];
int p[N],q[N];int main() {int index 0;while (scanf(%d, arr[index]) ! EOF);q[0] 1e6;int len 0;for (int i 1; i index; i) {int l 0, r len, mid, ans0;while (l r) {mid l (r - l) / 2;if (q[mid] arr[i]) {r mid - 1;}else {ans mid;l mid 1;}}len max(len, ans 1);q[ans 1] arr[i];}cout len endl;len 0;for (int i 1; i index; i) {int l 0, r len, mid, ans0;while (l r) {mid l (r - l) / 2;if (p[mid] arr[i]) {r mid - 1;}else {ans mid;l mid 1;}}len max(len, ans 1);p[ans 1] arr[i];}cout len endl;return 0;
}
