高校学风建设专栏网站,建设一批适合青少年的网站,长沙网站建设找哪家,建筑模板分为哪几类2.2 1.⼀和零 2.零钱兑换II 3.组合总和 Ⅳ 4.零钱兑换 5.完全平⽅数 6.封印 7.杨辉三角形 8.卡牌 9.最大子段和
题1#xff1a;https://leetcode.cn/problems/ones-and-zeroes/description/
01背包问题#xff0c;其中m#xff0c;n分别是背包的容量#xff0c;s字符串中…2.2 1.⼀和零 2.零钱兑换II 3.组合总和 Ⅳ 4.零钱兑换 5.完全平⽅数 6.封印 7.杨辉三角形 8.卡牌 9.最大子段和
题1https://leetcode.cn/problems/ones-and-zeroes/description/
01背包问题其中mn分别是背包的容量s字符串中的子串是物品的数量字符串的个数相当于物品的价值找最大的字符串个数
定义dp[i][j]最多有i个0和j个1的strs的最⼤⼦集的⼤⼩为dp[i][j]。
确定递推公式dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);
初始化由于是找个数所以都初始化为0 class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {int dp[101][101];memset(dp,0,sizeof(dp));for (string str:strs){int zeronum0,onenum0;for (char c:str){if (c0)zeronum;else onenum;}for (int im;izeronum;--i){for (int jn;jonenum;--j){dp[i][j]max(dp[i][j],dp[i-zeronum][j-onenum]1);}}}return dp[m][n];}
}; 题2https://leetcode.cn/problems/coin-change-ii/
由于可以无限拿所以是完全背包问题
问的是组合数那么是强调顺序了所以需要先遍历物品在遍历背包容量
定义dp[j]凑成总⾦额j的货币组合数为dp[j]
递推公式dp[j] dp[j - coins[i]];
初始化dp[0] 1因为如果为0的话后面的数都0这就也相当于当凑总金额为0的情况有1种 class Solution {
public:int change(int amount, vectorint coins) {vectorintdp(amount1,0);dp[0]1; //初始化for (int i0;icoins.size();i){for (int jcoins[i];jamount;j){dp[j]dp[j-coins[i]]; //dp[j] 就是所有的dp[j - coins[i]]考虑coins[i]的情况相加}}return dp[amount];}
}; 题3https://leetcode.cn/problems/combination-sum-iv/
这题找的排列数所以不在乎顺序所以需要先遍历背包容量在遍历物品
dp[i]: 凑成⽬标正整数为i的排列个数为dp[i]
dp[i] dp[i - nums[j]];
由于是找次数所以dp[0]要初始化为1
class Solution {public:int combinationSum4(vectorint nums, int target) {vectorint dp(target 1, 0);dp[0] 1;for (int i 0; i target; i) { // 遍历背包for (int j 0; j nums.size(); j) { // 遍历物品if (i - nums[j] 0 dp[i] INT_MAX - dp[i - nums[j]]) {dp[i] dp[i - nums[j]];}}}return dp[target];}
};
题4https://leetcode.cn/problems/coin-change/
这题不是找成功的个数了变成兑换成功的最小个数所以转移方程就要发生改变
dp[j]凑⾜总额为j所需钱币的最少个数为dp[j]
dp[j] min(dp[j - coins[i]] 1, dp[j]);
由于当金额为0的时候所需的钱一定是0所以dp[0] 0;
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorintdp(amount1,INT_MAX);dp[0]0;for (int i0;icoins.size();i){for (int jcoins[i];jamount;j){if (dp[j-coins[i]]!INT_MAX)dp[j]min(dp[j],dp[j-coins[i]]1);}}if (dp[amount]INT_MAX) return -1;return dp[amount];}
};
题5https://leetcode.cn/problems/perfect-squares/
dp[j]和为j的完全平⽅数的最少数量为dp[j]
dp[j] min(dp[j - i * i] 1, dp[j]);
当j为0的时候最小平方数的数量一定是0所以dp[0]⼀定是0
class Solution {
public:int numSquares(int n) {vectorintpp(101,0);for (int i1;i100;i)pp[i]i*i;vectorintdp(n1,INT_MAX);dp[0]0;for (int i1;i*in;i){for (int jpp[i];jn;j){if (dp[j-pp[i]]!INT_MAX)dp[j]min(dp[j],dp[j-pp[i]]1);}}return dp[n];}
};
题7封印https://www.luogu.com.cn/problem/P1934
题目背景
很久以前魔界大旱水井全部干涸温度也越来越高。为了拯救居民夜叉族国王龙溟希望能打破神魔之井进入人界“窃取”水灵珠以修复大地水脉。可是六界之间皆有封印神魔之井的封印由蜀山控制并施有封印。龙溟作为魔界王族习有穿行之术可任意穿行至任何留有空隙的位置。然而封印不留有任何空隙 龙溟无奈之下只能强行破除封印。破除封印必然消耗一定的元气。为了寻找水灵珠龙溟必须减少体力消耗。他可以在破除封印的同时使用越行术。
题目描述
神魔之井的封印共有 n 层每层封印都有一个坚固值。身为魔族的龙溟单独打破一层封印时需要消耗的元气为该层封印的坚固值和封印总层数 n 的平方的乘积 但他也可以打破第 i 层到第 j 层之间的所有封印( ij)总元气消耗为第 ,i,j 层封印的坚固值之和与第 ,i,j 层之间所有封印层包括第 ,i,j 层的坚固值之和的乘积但为了不惊动蜀山第 ,i,j 层封印的坚固值之和不能大于 t 单独打破可以不遵守。
输入格式
第一行包含两个正整数 n 和 t。 第二行有 n 个正整数第 i 个数为 ai表示第 i 层封印的坚固值。
输出格式
仅一行包含一个正整数表示最小消耗元气。
输入输出样例
输入 #1复制
6 10
8 5 7 9 3 5
输出 #1复制
578说明/提示
样例解释
先单独打破第一层再用越行术从第二层直接打破到最后一层。 这样消耗元气 8×62(55)×(57935)5788×62(55)×(57935)578。
数据范围
对于 10%10% 的数据 ≤10n≤10 对于 50%50% 的数据 ≤100n≤100 对于 70%70% 的数据 ≤500n≤500 对于 100%100% 的数据 ≤1000n≤1000 (1≤≤),≤20000ai(1≤i≤n),t≤20000。
思路当前状态的结果是由前一个状态转移来的
分为两种情况单独破或者多层一起破找两种情况的最小值
转移方程如下dp[i]mindp[i-1]a[i]*n*n,dp[j-1](a[i]a[j])*(f[i]-f[j-1])
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
const int N2e55;
int dp[N],a[N],f[N];
signed main(){int n,t;cinnt;for (int i1;in;i)cina[i];for (int i1;in;i)f[i]f[i-1]a[i];int mn*n;for (int i1;in;i){int ansdp[i-1]a[i]*m;for (int j1;ji-1;j){if (a[i]a[j]t) continue;else ansmin(ans,dp[j-1](a[i]a[j])*(f[i]-f[j-1]));}dp[i]ans;}coutdp[n];
}
题8杨辉三角形https://www.luogu.com.cn/problem/P8749
题目描述
下面的图形是著名的杨辉三角形: 思路找到杨辉三角里面值和位置的关系然后二分找
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
int n;
int C(int x,int y){int res1;for (int ix,j1;jy;j,--i){resres*i/j;if (resn)return res;}return res;
}
signed main(){cinn;if (n1){cout1;return 0;}for (int i16;i0;--i){int l2*i,r1e9;while (lr){int midl(r-l)/2;int xC(mid,i);if (xn){printf(%lld,(mid1)*mid/2i1);return 0;}else if (xn)lmid1;else if (xn)rmid-1;}}return 0;
}题9卡牌https://www.luogu.com.cn/problem/P8800
题目描述
这天小明在整理他的卡牌。
他一共有 n 种卡牌第 i 种卡牌上印有正整数数 (∈[1,])i(i∈[1,n]), 且第 i 种卡牌现有 ai 张。
而如果有 n 张卡牌其中每种卡牌各一张那么这 n 张卡牌可以被称为一套牌。小明为了凑出尽可能多套牌拿出了 m 张空白牌, 他可以在上面写上数 i将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观决定第 i 种牌最多手写 bi 张。
请问小明最多能凑出多少套牌?
输入格式
输入共 3 行第一行为两个正整数 nm 。
第二行为 n 个正整数 1,2,…,a1,a2,…,an 。
第三行为 n 个正整数 1,2,…,b1,b2,…,bn 。
输出格式
一行一个整数表示答案。
输入输出样例
输入 #1复制
4 5
1 2 3 4
5 5 5 5
输出 #1复制
3
说明/提示
【样例说明】
这 55 张空白牌中拿 22 张写 11拿 11 张写 22这样每种牌的牌数就变为了 3,3,3,43,3,3,4可以凑出 33 套牌剩下 22 张空白牌不能再帮助小明凑出一套。
【评测用例规模与约定】
对于 30%30% 的数据保证 ≤2000n≤2000;
对于 100%100% 的数据保证 ≤2×105;,≤;≤2n≤2×105;ai,bi≤n;m≤n2 。
思路主要还是用二分假定最终有x副牌然后根据x去找每种牌如果超过了给牌范围就返回不行或者说如果总数超过了给牌范围也返回不行
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
const int N2e55;
int a[N],b[N],m,n,l0,r1e75;
bool check(int x){ //可以形成x副牌 int sum0;for (int i0;in;i){if (x-a[i]b[i])return false;summax(x-a[i],0LL);}if (summ)return true;else return false;
}
int solve(){while (lr){int midl(r-l)/2;if (check(mid)){lmid1;}else {rmid;}}if (check(r))return r;else return l;
}
signed main(){cinnm;for (int i0;in;i)cina[i];for (int i0;in;i)cinb[i];coutsolve()-1;
}
题10最大子段和https://www.luogu.com.cn/problem/P1115
题目描述
给出一个长度为 n 的序列 a选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数表示序列的长度 n。
第二行有 n 个整数第 i 个整数表示序列的第 i 个数字 ai。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1复制
7
2 -4 3 -1 2 -4 3输出 #1复制
4
说明/提示
样例 1 解释
选取 [3,5][3,5] 子段 {3,−1,2}{3,−1,2}其和为 44。
数据规模与约定
对于 40%40% 的数据保证 ≤2×103n≤2×103。对于 100%100% 的数据保证 1≤≤2×1051≤n≤2×105−104≤≤104−104≤ai≤104。
思路动态规划遍历一遍数组找到最大的连续子段和然后再遍历一遍dp数组找到最大值
#include bits/stdc.h
using namespace std;
#define lowbit(x) (x - (x))
#define int long long
const int N2e55;
int dp[N],a[N];
signed main(){int n;cinn;for (int i1;in;i)cina[i];dp[1]a[1];int maxndp[1];for (int i1;in;i){dp[i]max(dp[i-1]a[i],a[i]);if (dp[i]maxn)maxndp[i];}coutmaxn;
}
