每道题都在洛谷上，每个题都有很详细的题解，可以先自行做，不会再看题解。
题目解析思路都写在代码中，中文题面就不单独解释题意了。
P2440 木材加工（二分答案）
链接：P2440 木材加工
解析 代码
#include<iostream>
#include<algorithm>
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) / 2
if(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,至少得将其减小至x
ans += 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 i=1;i<=n - 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 - 1
ans = 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 i=1;i<=n;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_queue<int, vector<int>, greater<int>>q;//小顶堆
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;
}
