引用：牛客BGN54 牛牛与切割机
描述
有一个序列 a1,a2,...,ana1,a2,...,an ， 牛牛将对这个序列切割一刀（划分分成两个不相交的非空序列，一个序列为 a1,…,apa1,…,ap，另一个序列为 ap+1,…,anap+1,…,an），牛牛切割的代价为两个序列元素和的乘积。牛牛想知道切割代价最小是多少。
输入描述：
第一行输入一个整数 n，表示序列的长度 2≤n≤10^6
第二行输入 nn 个整数 a1,a2,…,ana1,a2,…,an，表示序列的元素 −10^3≤ai≤10^3.
输出描述：
输出一个整数表示切割代价最小是多少。
示例1
输入：
5 1 2 3 4 5
复制输出：
14
复制说明：
序列被划分为1 和 2 3 4 5，右边和为 14。
示例2
输入：
4 2 1 3 4
复制输出：
16
复制说明：
序列被划分为 2 和 1 3 4。
这个题我觉得是数学问题，我要求切成两快的和乘积最大，那我设数组所有数的和为Sum,切出来的左边的和为Sum1,右边就是Sum-Sum1,其实就是要求Sum1*(Sum-Sum1)的最小值，那就是二次函数求解，其实二次函数的中心值Sum*Sum/4一般取不到，所以还是动态更新最小值去解：
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin>>n; long sum=0; vector<int> a(n); for(int i=0;i<n;i++) { cin>>a[i]; sum+=a[i]; } long Min=LONG_MAX;//这个题乘出来的数据量有可能很大，至少要用long。 long sum1=0; for(int i=0;i<n-1;i++){//因为我至少要有两段，所以是n-1,就是说我一段的长度最多为n-1 sum1+=a[i]; long cost=sum1*(sum-sum1); if(Min>cost) Min=cost;//动态取最小值 } cout<<Min<<endl; return 0; }Java代码：用Java的时候，我常常犯一个毛病，就是BufferedReader 一读就是一行，要是一行有多个数字，就要切割了，常常输入格式错误哭~~~
import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); PrintWriter out=new PrintWriter(System.out); StringTokenizer st=new StringTokenizer(br.readLine()); int n=Integer.parseInt(st.nextToken()); int [] arr=new int [n]; long sum=0; st=new StringTokenizer(br.readLine()); for(int i=0;i<n;i++){ arr[i]=Integer.parseInt(st.nextToken()); sum+=arr[i]; } long Min=Long.MAX_VALUE; long sum1=0; for(int i=0;i<n-1;i++){ sum1+=arr[i]; long cost=sum1*(sum-sum1); Min=Math.min(cost,Min); } out.print(Min); out.flush(); br.close(); out.close(); } }注：其实这个题不用考虑负数乘出来负负得正的影响，因为我们考虑了所有的切点，还是[-2,3,-4],这个样列，我3个数一共两种情况，[-2],[3,-4]和[-2,3],[-4],结果为2和-4，那按我们的动态取最小值就是-4，没有必要考虑有负数的
引用洛谷P1182：数列分段 Section II
## 题目描述
对于给定的一个长度为 N 的正整数数列 A_{1~N}，现要将其分成 M（M<=N）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 4 2 4 5 1 要分成 3段。
将其如下分段：
[4 2][4 5][1]
第一段和为 6，第 2 段和为 9，第 3段和为 1，和最大值为 9。
将其如下分段：
[4][2 4][5 1]
第一段和为 4，第 2 段和为 6，第 3段和为 6，和最大值为 6。
并且无论如何分段，最大值不会小于 6。
所以可以得到要将数列 4 2 4 5 1要分成 3段，每段和的最大值最小为 6。
## 输入格式
第 1行包含两个正整数 N,M。
第 2 行包含 N 个空格隔开的非负整数 A_i，含义如题目所述。
## 输出格式
一个正整数，即每段和最大值最小为多少。
## 输入输出样例 #1
### 输入 #1
5 3
4 2 4 5 1
### 输出 #1
6
## 说明/提示
对于 20% 的数据，N<=10。
对于 40% 的数据，N<=1000。
对于 100% 的数据，1<= N<= 10^5，M<=N，A_i < 10^8， 答案不超过 10^9。
这个题一开始我也看了半天，在想咋写呢，其实这个题的思路真的是妙不可言，我们要求每段和的最大值的最小值，其实，可以反过来想，就是我已知一个加和最大值，对这个数组至少要切多少段才能满足每一段的加和都小于这个已知最大值，这个题他给了我一个切的段数，那么我在已知次最大值下，能让我取出来满足每一段加和都小于他至少要的段数比题目给的M小，就说明他是可行的，所以这里要二分，一般来说二分答案法的left取0（这个题其实可以取数字最大值），right取数组最大值（但这个题要的right=数组加和，因为我可以一刀都不切，那就是全部数组），也就是说我先得到一个mid=left+(right-left),让他作为我们已知的加和最大值，然后如果切出来的每一组的加和都小于Mid的段数<=M,那么我们就知道有这个值为最大值的最小情况数可行的，那么我们继续缩小mid,也就是去找更小的可能，如果>M了，那我们以这个mid为最小值的最大情况就太小了，相当于一个砍树的上限，就是在这个标准下我们砍树的总数到不了需要的值，我们就增大他，这里就left=mid+1就行了，就是取更大的去找他的答案。
代码如下：
#include <bits/stdc++.h> using namespace std; //必须让数组每一部分都小于等于aim，请问要划几个部分才够？返回部分个数 // 功能：给定一个最大和限制aim，用贪心策略计算： // 将数组分割成若干连续段，且每段和 ≤ aim 时，最少需要分割成多少段 // 如果存在单个元素 > aim，说明该aim不合法，返回INT_MAX int fun(vector<int> nums,long aim) { int parts=1; // 初始段数为1，整个数组默认是一段 int all=0; // 记录当前段的累加和 for (int i=0;i<nums.size();i++) { if (nums[i]>aim) { return INT_MAX;//如果我们有单个数组元素已经大于aim，则当前aim无法满足，直接返回极大值 } if (all+nums[i]>aim) {//相当于滑动窗口，我一直吸纳元素，如果已经大于aim了，那我要重制all（窗口和） parts++;//让我的分割部分加一 all=nums[i];// 开启新的一段，当前段和重置为当前元素 }else { all+=nums[i];//如果还是小于等于aim，则继续吸纳元素，当前段和累加 } } return parts;//返回满足条件的最少分割部分个数 } //接下来我们进行二分，就是说我们解这道题时，要求我们找数组分割为k段的每段子数组加和最大值的最小值情况 //比如：[6,5,5,4],k=2,可以分割为[6,5],[5,4]，也可以分割为[6,5,5],[4]，显然第一种情况是符合题意的 //所以我们二分，就是在特定割为k段的情况下，去二分寻找能让每段和最大值最小的答案 // 函数功能：二分查找答案，求解分割为k段时，最小的最大子数组和（最大值最小化问题） int splitArray(vector<int> nums,int k) { long sum=0; for (int i=0;i<nums.size();i++) { sum+=nums[i]; // 计算数组总和，作为二分的右边界 } long ans=0; // 存储最终的答案 // 二分框架：左边界l=0，右边界r=数组总和，m为中间值，need为需要的分段数 for (long l=0,r=sum,m,need;l<=r;) { m=l+(r-l)/2; // 计算中间值，避免溢出，作为当前尝试的答案 need=fun(nums,m); // 计算最大和为m时，最少需要分多少段 if (need<=k) { // 需要的分段数 ≤ 要求的k段：说明m是可行解 ans=m; // 记录当前可行的答案 r=m-1; // 尝试寻找更小的可行值，收缩右边界 }else { // 需要的分段数 > 要求的k段：说明m太小，不可行 l=m+1; // 需要增大m，收缩左边界 } } return (int)ans; // 返回最终找到的最小最大和 } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,k; // n：数组长度，k：需要分割的段数 cin>>n>>k; vector<int> nums(n); for (int i=0;i<n;i++) { cin>>nums[i]; // 读取数组元素 } cout<<splitArray(nums,k)<<endl; // 输出答案 }java代码：
import java.util.*; import java.io.*; public class Main { // 功能：给定一个最大和限制limit，用贪心策略计算： // 将数组分割成若干连续段，且每段和 ≤ limit 时，最少需要分割成多少段 // 如果存在单个元素 > limit，说明该limit不合法，返回Integer.MAX_VALUE public static int getCount(int[] arr, long limit) { int parts = 1; // 初始段数为1，整个数组默认是一段 long sum = 0; // 记录当前段的累加和 for (int num : arr) { if (num > limit) { return Integer.MAX_VALUE; // 单个元素超过限制，无法满足 } if (sum + num > limit) { // 当前段和+当前元素超过限制，需要分段 parts++; // 分割部分+1 sum = num; // 开启新段，当前段和重置为当前元素 } else { sum += num; // 未超限制，继续累加当前段 } } return parts; // 返回满足条件的最少段数 } // 二分答案：求解分割为k段时，最小的最大子数组和（最大值最小化问题） public static int splitArray(int[] arr, int k) { long left = 0; // 左边界：数组中的最大值（至少要能放下最大元素） long right = 0; // 右边界：数组总和（不分段时的最大和） for (int num : arr) { if (num > left) { left = num; } right += num; } long res = 0; // 存储最终答案 while (left <= right) { long mid = left + (right - left) / 2; // 防溢出，当前尝试的最大和 int parts = getCount(arr, mid); // 计算当前mid下最少需要的段数 if (parts <= k) { // 分段数≤k：mid可行，尝试找更小的最大值 res = mid; right = mid - 1; } else { // 分段数>k：mid太小，需要增大 left = mid + 1; } } return (int) res; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PrintWriter out = new PrintWriter(System.out); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); // 数组长度 int k = Integer.parseInt(st.nextToken()); // 要求分割的段数 int[] arr = new int[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken()); } out.println(splitArray(arr, k)); out.flush(); br.close(); out.close(); } }引用：我们作业里的一道题：6-9 小宇的零食选购计划
题目描述
小宇去超市买零食，货架上按顺序摆放着 n 包不同的零食，每包零食都有一个快乐值（正数）。小宇有一个小习惯：不能连续拿两包相邻的零食（比如拿了第 1 包就不能拿第 2 包，拿了第 3 包就不能拿第 2、4 包）。
请你帮小宇计算，他最多能获得的总快乐值是多少？
输入格式
第一行输入一个正整数 (1≤n≤1000))，表示零食的数量。
第二行输入 n 个正整数 (a1,a2,...,an)，表示每包零食的快乐值（1≤快乐值≤1000）。
输出格式
输出一个整数，表示小宇能获得的最大总快乐值。
输入样例
在这里给出一组输入。例如：
5 1 2 3 4 5输出样例
在这里给出相应的输出。例如：
9这个题不说和力扣里的打家劫舍一模一样，也是完全相似，本质上还是定义一个dp数组来记录最大值，你啥也不买，那就是0啊，你只买一件，dp就是来记录状态的，就是我只看前多少个数，他现在最大值，那只取一件，那就是第一个数啊，随后我们看到第i件的时候，由于我们的下标从0开始，所以第i件就是第i-1个物品，那我们再取的时候，要么就取i-1件，那旁边的不能要，要是要了，那i-1的就不要，用一个sum加和来动态更新最大值及可，所以代码如下：
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vector<int> nums(n); for (int i=0;i<n;i++) cin>>nums[i]; vector<int> dp(n+1,0); dp[0]=0; dp[1]=nums[0]; if (n==0) cout<<0<<endl;//我一个都不要就是0 else if (n==1) cout<<nums[0]<<endl;//我只看第一个那就是第一个 else for (int i=2;i<=n;i++) {//从而开始，要么我就要他，要么我不要他 //dp[i-1]就是我不取它，就是前一个的最大值，dp[i-2]+nums[i-1]就是取它，就是前一个最大值加我这个数 dp[i]=max(dp[i-1],dp[i-2]+nums[i-1]);//不断更行就行 } cout<<dp[n]<<endl;//因为n从0开始，所以就是dp[n]. return 0; }java代码如下：
import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); PrintWriter out=new PrintWriter(System.out); StringTokenizer st=new StringTokenizer(br.readLine()); int n=Integer.parseInt(st.nextToken()); int [] arr=new int [n]; st=new StringTokenizer(br.readLine()); for(int i=0;i<n;i++){ arr[i]=Integer.parseInt(st.nextToken()); } int []dp=new int [n+1]; dp[0]=0; dp[1]=arr[0]; for(int i=2;i<=n;i++){ dp[i]=Math.max(dp[i-1],dp[i-2]+arr[i-1]); } out.print(dp[n]); out.flush(); br.close(); out.close(); } }这些题都是我在写的时候想了比较久的题目，特别第二道，真的有点晕，梳理思路要时间，所以我写在这里，就是要有常来写写过的题来温故知新，欸，加油啊。
技术解析与DNS隐私保护实践)
