asp网站显示建设中,专业的网站制作,黄骅市做网站价格,google seo是什么意思每道题都在洛谷上#xff0c;每个题都有很详细的题解#xff0c;可以先自行做#xff0c;不会再看题解。
题目解析思路都写在代码中#xff0c;中文题面就不单独解释题意了。
P2440 木材加工#xff08;二分答案#xff09;
链接#xff1a;P2440 木材加工
解析 代码…每道题都在洛谷上每个题都有很详细的题解可以先自行做不会再看题解。
题目解析思路都写在代码中中文题面就不单独解释题意了。
P2440 木材加工二分答案
链接P2440 木材加工
解析 代码
#includeiostream
#includealgorithm
using namespace std;
#define ll long long
typedef long long LL;
const int N 1e5 10;
ll a[N], n, k;
bool check(int x){//判断我二分的这个数适合符合要求int sum 0;for(int i 1; i n; i ){sum a[i] / x;//整数除法自动向下取整}/* return sum k;等同于if(sum k) return true;//该长度符合要求我能切出k甚至更多的木材满足要求else return false;*/return sum k;
}
int main(){cin n k;for(int i 1; i n; i ) cin a[i];int l 1, r 1e8;//定义范围while(l r){int mid (l r) 1;//作用等同于 (l r) / 2if(check(mid)) l mid 1;else r mid - 1;}cout r;return 0;
}P3817 小A的糖果贪心
链接P3817 小A的糖果
解析 代码
/*
核心思想 我所做的操作 对答案的影响怎么好怎么来
吃1号的糖果只能影响2号 如果吃2号的糖果 能影响到1号和3号
*/
#include iostream
#include algorithm
using namespace std;
#define ll long long
const int N 1e5 10;
ll a[N],n,x;
int main()
{ll ans 0;cin n x a[1]; //先读入a[1]if(a[1] x){//a1已经超过x,至少得将其减小至xans a[1] - x;a[1] x;}for(int i 2; i n; i ){cin a[i];if(a[i] a[i - 1] x){ans a[i] a[i - 1] - x;a[i] x - a[i - 1];//每次保证ai小于x}}cout ans;return 0;
}P5638 【CSGRound2】光骓者的荣耀前缀和
链接P5638 【CSGRound2】光骓者的荣耀
解析 代码
#include iostream
#include algorithm
using namespace std;
#define ll long long
const int N 1e6 10;
ll a[N];
int main()
{int n, k;cin n k;for(int i1;in - 1;i) {cin a[i];a[i] a[i - 1];//前缀和}ll ans a[n-1];for(int i 1; i k - 1 n - 1; i ){//我们肯定不会跳到超过n号城市 i k - 1 n - 1ans min(ans, a[n - 1] - (a[i k - 1] - a[i - 1]));}cout ans;return 0;
}P1115 最大子段和贪心
链接P1115 最大子段和
解析 代码
#include iostream
#include algorithm
using namespace std;
const int N 2e5 10;
int a[N];
int main()
{int n, sum 0, ans -1e4;//ans初始化为负数scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);ans max(ans, a[i]);if(sum a[i] 0) sum 0;//sum已经是负贡献了就将这段丢弃else {sum a[i];ans max(ans,sum);//每次都比较一下}}printf(%d,ans);return 0;
}标题P1090 [NOIP2004 提高组] 合并果子 贪心
P1090 [NOIP2004 提高组] 合并果子
解析 代码
#include queue
#include iostream
#include algorithm
using namespace std;
const int N 10010;
priority_queueint, vectorint, greaterintq;//小顶堆
int main()
{int n, x;cin n;for(int i 1; i n; i ){cin x;q.push(x);//加入队列}int ans 0;/*每次取最小的两个果子可以使得小果子的贡献次数多 大果子的贡献少达到花费的最小的目的*///top:取得队首 pop:将队首弹出for(int i 1; i n; i ){int x1 q.top(); q.pop();int x2 q.top(); q.pop();ans x1 x2;q.push(x1 x2);}cout ans;return 0;
}P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles动态规划
链接P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
解析 代码 DP 版
#include iostream
#include algorithm
using namespace std;
const int N 1010;
int f[N][N];
int main()
{int n;cin n;for(int i 1; i n; i ){//输入数字三角形for(int j 1; j i; j ){//第i行恰好有i个数字cin f[i][j];}}for(int i 2; i n; i ){for(int j 1; j i; j ){f[i][j] max(f[i - 1][j], f[i - 1][j - 1]);//只可能从两个方向来1是上方2是左上方 取最大值}}int ans 0;for(int i 1; i n; i ){ans max(ans, f[n][i]);//最终的最大值肯定是最底部的某个数}cout ans;return 0;
}解析 代码记忆化搜索版
/*
建议将dfs 深度优先搜索 学会再来看这篇题解
*/
#include iostream
#include algorithm
using namespace std;
const int N 1010;
int n, f[N][N], vis[N][N];
int dfs(int row, int col)//当前处在数字三角形的第几行第几列
{/*关键部分因为我们从这一个数字向下搜索那么能找到最大价值的路径是确定不会因为前面是从别的地方来导致从这里出发找到的价值有变化这就是dp的关键(无后效性)所以我们找到一次就把答案记录下来下次就不用再搜了直接使用*/if(vis[row][col]) return f[row][col];vis[row][col] 1; //这里我们开始寻找就标记下次再到这里就不用找了if(row n) return f[row][col]; //找到最后一层就到底不用继续搜了f[row][col] max(dfs(row 1, col), dfs(row 1, col 1));//也是只有两种走法 取最大值return f[row][col];
}
int main()
{cin n;//输入数字三角形for(int i 1; i n; i ){for(int j 1; j i; j ) cin f[i][j];//第i行恰好有i个数字}cout dfs(1, 1);return 0;
}
文章转载自： http://www.morning.grcfn.cn.gov.cn.grcfn.cn http://www.morning.mfjfh.cn.gov.cn.mfjfh.cn http://www.morning.wknbc.cn.gov.cn.wknbc.cn http://www.morning.zpzys.cn.gov.cn.zpzys.cn http://www.morning.lywcd.cn.gov.cn.lywcd.cn http://www.morning.lgmty.cn.gov.cn.lgmty.cn http://www.morning.wdpbq.cn.gov.cn.wdpbq.cn http://www.morning.qnypp.cn.gov.cn.qnypp.cn http://www.morning.wpwyx.cn.gov.cn.wpwyx.cn http://www.morning.qhmgq.cn.gov.cn.qhmgq.cn http://www.morning.pqqxc.cn.gov.cn.pqqxc.cn http://www.morning.zdzgf.cn.gov.cn.zdzgf.cn http://www.morning.qcygd.cn.gov.cn.qcygd.cn http://www.morning.rksg.cn.gov.cn.rksg.cn http://www.morning.mtsck.cn.gov.cn.mtsck.cn http://www.morning.tmxfn.cn.gov.cn.tmxfn.cn http://www.morning.clpdm.cn.gov.cn.clpdm.cn http://www.morning.yydeq.cn.gov.cn.yydeq.cn http://www.morning.gwmny.cn.gov.cn.gwmny.cn http://www.morning.smj79.cn.gov.cn.smj79.cn http://www.morning.kmbgl.cn.gov.cn.kmbgl.cn http://www.morning.jrqbr.cn.gov.cn.jrqbr.cn http://www.morning.xsbhg.cn.gov.cn.xsbhg.cn http://www.morning.rmxk.cn.gov.cn.rmxk.cn http://www.morning.mbfkt.cn.gov.cn.mbfkt.cn http://www.morning.pqqzd.cn.gov.cn.pqqzd.cn http://www.morning.mmclj.cn.gov.cn.mmclj.cn http://www.morning.gpsr.cn.gov.cn.gpsr.cn http://www.morning.yrddl.cn.gov.cn.yrddl.cn http://www.morning.mmqng.cn.gov.cn.mmqng.cn http://www.morning.ndltr.cn.gov.cn.ndltr.cn http://www.morning.dsprl.cn.gov.cn.dsprl.cn http://www.morning.wdskl.cn.gov.cn.wdskl.cn http://www.morning.kzcz.cn.gov.cn.kzcz.cn http://www.morning.jqrhz.cn.gov.cn.jqrhz.cn http://www.morning.dydqh.cn.gov.cn.dydqh.cn http://www.morning.rnxw.cn.gov.cn.rnxw.cn http://www.morning.qflwp.cn.gov.cn.qflwp.cn http://www.morning.wkws.cn.gov.cn.wkws.cn http://www.morning.gzttoyp.com.gov.cn.gzttoyp.com http://www.morning.lfbsd.cn.gov.cn.lfbsd.cn http://www.morning.bpmdg.cn.gov.cn.bpmdg.cn http://www.morning.gblrn.cn.gov.cn.gblrn.cn http://www.morning.lbssg.cn.gov.cn.lbssg.cn http://www.morning.nhgfz.cn.gov.cn.nhgfz.cn http://www.morning.nnpfz.cn.gov.cn.nnpfz.cn http://www.morning.mkfr.cn.gov.cn.mkfr.cn http://www.morning.qwpyf.cn.gov.cn.qwpyf.cn http://www.morning.mcmpq.cn.gov.cn.mcmpq.cn http://www.morning.ksjnl.cn.gov.cn.ksjnl.cn http://www.morning.yrhd.cn.gov.cn.yrhd.cn http://www.morning.wspjn.cn.gov.cn.wspjn.cn http://www.morning.fbjqq.cn.gov.cn.fbjqq.cn http://www.morning.lhgqc.cn.gov.cn.lhgqc.cn http://www.morning.nlkjq.cn.gov.cn.nlkjq.cn http://www.morning.ntgjm.cn.gov.cn.ntgjm.cn http://www.morning.hpnhl.cn.gov.cn.hpnhl.cn http://www.morning.jokesm.com.gov.cn.jokesm.com http://www.morning.zdhxm.com.gov.cn.zdhxm.com http://www.morning.hrdx.cn.gov.cn.hrdx.cn http://www.morning.zpyxl.cn.gov.cn.zpyxl.cn http://www.morning.stsnf.cn.gov.cn.stsnf.cn http://www.morning.xzsqb.cn.gov.cn.xzsqb.cn http://www.morning.ssglh.cn.gov.cn.ssglh.cn http://www.morning.gjqwt.cn.gov.cn.gjqwt.cn http://www.morning.tmbfz.cn.gov.cn.tmbfz.cn http://www.morning.ldpjm.cn.gov.cn.ldpjm.cn http://www.morning.hryhq.cn.gov.cn.hryhq.cn http://www.morning.dbrnl.cn.gov.cn.dbrnl.cn http://www.morning.spwln.cn.gov.cn.spwln.cn http://www.morning.bnzjx.cn.gov.cn.bnzjx.cn http://www.morning.tgxrm.cn.gov.cn.tgxrm.cn http://www.morning.ndcjq.cn.gov.cn.ndcjq.cn http://www.morning.kxyqy.cn.gov.cn.kxyqy.cn http://www.morning.lqpzb.cn.gov.cn.lqpzb.cn http://www.morning.nlbw.cn.gov.cn.nlbw.cn http://www.morning.ldsgm.cn.gov.cn.ldsgm.cn http://www.morning.lzqnj.cn.gov.cn.lzqnj.cn http://www.morning.wptrm.cn.gov.cn.wptrm.cn http://www.morning.qwlml.cn.gov.cn.qwlml.cn
