洛谷-【动态规划1】动态规划的引入4

P1077 [NOIP 2012 普及组] 摆花题目描述小明的花店新开张为了吸引顾客他想在花店的门口摆上一排花共 m 盆。通过调查顾客的喜好小明列出了顾客最喜欢的 n 种花从 1 到 n 标号。为了在门口展出更多种花规定第 i 种花不能超过 ai​ 盆摆花时同一种花放在一起且不同种类的花需按标号的从小到大的顺序依次摆列。试编程计算一共有多少种不同的摆花方案。输入格式第一行包含两个正整数 n 和 m中间用一个空格隔开。第二行有 n 个整数每两个整数之间用一个空格隔开依次表示 a1​,a2​,⋯,an​。输出格式一个整数表示有多少种方案。注意因为方案数可能很多请输出方案数对 1067 取模的结果。输入输出样例输入 #1复制2 4 3 2输出 #1复制2说明/提示【数据范围】对于 20% 数据有 0n≤8,0m≤8,0≤ai​≤8。对于 50% 数据有 0n≤20,0m≤20,0≤ai​≤20。对于 100% 数据有 0n≤100,0m≤100,0≤ai​≤100。NOIP 2012 普及组 第三题实现代码#includebits/stdc.h using namespace std; const int maxn105, mod 1000007; int n, m, a[maxn], f[maxn][maxn]; int main() { cinnm; for(int i1; in; i) cina[i]; f[0][0] 1; for(int i1; in; i) for(int j0; jm; j) for(int k0; kmin(j, a[i]); k) f[i][j] (f[i][j] f[i-1][j-k])%mod; coutf[n][m]endl; return 0; }P3842 [TJOI2007] 线段题目描述在一个 n×n 的平面上在每一行中有一条线段第 i 行的线段的左端点是 (i,Li​)右端点是 (i,Ri​)。你从 (1,1) 点出发要求沿途走过所有的线段最终到达 (n,n) 点且所走的路程长度要尽量短。更具体一些说你在任何时候只能选择向下走一步行数增加 1、向左走一步列数减少 1或是向右走一步列数增加 1。当然由于你不能向上行走因此在从任何一行向下走到另一行的时候你必须保证已经走完本行的那条线段。输入格式第一行有一个整数 n。以下 n 行在第 i 行总第 (i1) 行的两个整数表示 Li​ 和 Ri​。输出格式仅包含一个整数你选择的最短路程的长度。输入输出样例输入 #1复制6 2 6 3 4 1 3 1 2 3 6 4 5输出 #1复制24说明/提示我们选择的路线是(1, 1) (1, 6) (2, 6) (2, 3) (3, 3) (3, 1) (4, 1) (4, 2) (5, 2) (5, 6) (6, 6) (6, 4) (6, 6)不难计算得到路程的总长度是 24。对于 100% 的数据1≤n≤2×1041≤Li​≤Ri​≤n。实现代码#include iostream #include cstdio #define rep(i,m,n) for(int im;in;i) using namespace std; inline int read(){ int s 0, w 1; char ch getchar(); while(ch 0 || ch 9){if(ch -)w -1;ch getchar();} while(ch 0 ch 9) s s * 10 ch - 0,ch getchar(); return s * w; } const int MAXN 20010; int n; int l[MAXN], r[MAXN], f[MAXN][2]; int main(){ n read(); rep(i, 1, n) l[i] read(), r[i] read(); f[1][0] r[1] r[1] - l[1] - 1; f[1][1] r[1] - 1; rep(i, 2, n) f[i][0] min(f[i-1][0] abs(l[i-1] - r[i]) r[i] - l[i] 1, f[i-1][1] abs(r[i-1] - r[i]) r[i] - l[i] 1), f[i][1] min(f[i-1][0] abs(l[i-1] - l[i]) r[i] - l[i] 1, f[i-1][1] abs(r[i-1] - l[i]) r[i] - l[i] 1); printf(%d\n, min(f[n][0] n - l[n], f[n][1] n - r[n])); return 0; }P1064 [NOIP 2006 提高组] 金明的预算方案题目描述金明今天很开心家里购置的新房就要领钥匙了新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是妈妈昨天对他说“你的房间需要购买哪些物品怎么布置你说了算只要不超过 n 元钱就行”。今天一早金明就开始做预算了他把想买的物品分为两类主件与附件附件是从属于某个主件的下表就是一些主件与附件的例子主件附件电脑打印机扫描仪书柜图书书桌台灯文具工作椅无如果要买归类为附件的物品必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。每个附件对应一个主件附件不再有从属于自己的附件。金明想买的东西很多肯定会超过妈妈限定的 n 元。于是他把每件物品规定了一个重要度分为 5 等用整数 1∼5 表示第 5 等最重要。他还从因特网上查到了每件物品的价格都是 10 元的整数倍。他希望在不超过 n 元的前提下使每件物品的价格与重要度的乘积的总和最大。设第 j 件物品的价格为 vj​重要度为 wj​共选中了 k 件物品编号依次为 j1​,j2​,…,jk​则所求的总和为vj1​​×wj1​​vj2​​×wj2​​⋯vjk​​×wjk​​请你帮助金明设计一个满足要求的购物单。输入格式第一行有两个整数分别表示总钱数 n 和希望购买的物品个数 m。第 2 到第 (m1) 行每行三个整数第 (i1) 行的整数 vi​pi​qi​ 分别表示第 i 件物品的价格、重要度以及它对应的的主件。如果 qi​0表示该物品本身是主件。输出格式输出一行一个整数表示答案。输入输出样例输入 #1复制1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0输出 #1复制2200说明/提示数据规模与约定对于全部的测试点保证 1≤n≤3.2×1041≤m≤600≤vi​≤1041≤pi​≤50≤qi​≤m答案不超过 2×105。NOIP 2006 提高组 第二题实现代码#include iostream #include algorithm const int kMaxN 32000, kMaxM 60; int v[kMaxM 5][3], p[kMaxM 5][3]; int f[kMaxN 5]; int main() { int n, m; std::cin n m; for (int i 1; i m; i) { int _v, _p, _q; std::cin _v _p _q; if (!_q) { v[i][0] _v; p[i][0] _p; } else { if (v[_q][1] 0) { v[_q][1] _v; p[_q][1] _p; } else { v[_q][2] _v; p[_q][2] _p; } } } for (int i 1; i m; i) for (int j n; j 0; --j) { auto cost2 [v, p, i](int x, int y) { return v[i][x] v[i][y]; }; auto cost3 [v, p, i](int x, int y, int z) { return v[i][x] v[i][y] v[i][z]; }; auto rpp [v, p, i](int x) { return v[i][x] * p[i][x]; }; if (j v[i][0]) f[j] std::max(f[j], f[j - v[i][0]] rpp(0)); if (j cost2(0, 1)) f[j] std::max(f[j], f[j - cost2(0, 1)] rpp(0) rpp(1)); if (j cost2(0, 2)) f[j] std::max(f[j], f[j - cost2(0, 2)] rpp(0) rpp(2)); if (j cost3(0, 1, 2)) f[j] std::max(f[j], f[j - cost3(0, 1, 2)] rpp(0) rpp(1) rpp(2)); } std::cout f[n] std::endl; }P2392 kkksc03考前临时抱佛脚题目背景kkksc03 的大学生活非常的颓废平时根本不学习。但是临近期末考试他必须要开始抱佛脚以求不挂科。题目描述这次期末考试kkksc03 需要考 4 科。因此要开始刷习题集每科都有一个习题集分别有 s1​,s2​,s3​,s4​ 道题目完成每道题目需要一些时间可能不等A1​,A2​,…,As1​​B1​,B2​,…,Bs2​​C1​,C2​,…,Cs3​​D1​,D2​,…,Ds4​​。kkksc03 有一个能力他的左右两个大脑可以同时计算 2 道不同的题目但是仅限于同一科。因此kkksc03 必须一科一科的复习。由于 kkksc03 还急着去处理洛谷的 bug因此他希望尽快把事情做完所以他希望知道能够完成复习的最短时间。输入格式本题包含 5 行数据第 1 行为四个正整数 s1​,s2​,s3​,s4​。第 2 行为 A1​,A2​,…,As1​​ 共 s1​ 个数表示第一科习题集每道题目所消耗的时间。第 3 行为 B1​,B2​,…,Bs2​​ 共 s2​ 个数。第 4 行为 C1​,C2​,…,Cs3​​ 共 s3​ 个数。第 5 行为 D1​,D2​,…,Ds4​​ 共 s4​ 个数意思均同上。输出格式输出一行为复习完毕最短时间。输入输出样例输入 #1复制1 2 1 3 5 4 3 6 2 4 3输出 #1复制20说明/提示1≤s1​,s2​,s3​,s4​≤20。1≤A1​,A2​,…,As1​​,B1​,B2​,…,Bs2​​,C1​,C2​,…,Cs3​​,D1​,D2​,…,Ds4​​≤60。实现代码#includebits/stdc.h using namespace std; const int N1e3; int s[N]; int a[N][N]; int mark[5]{0,1200,1200,1200,1200}; void dfs(int left,int right,int sum,int n){ if(sums[n]){ mark[n]min(max(left,right),mark[n]); return ; } sum; dfs(lefta[n][sum],right,sum,n); dfs(left,righta[n][sum],sum,n); } int main(){ for(int i1;i4;i){ cins[i]; } for(int i1;i4;i){ for(int j1;js[i];j){ cina[i][j]; } } for(int i1;i4;i){ dfs(0,0,0,i); } int cnt0; for(int i1;i4;i){ cntmark[i]; } coutcnt; return 0; }