--- title: 整数划分 date: 1729351019301 tags: [Life] [Coding] [Algorithms] author: TalexDS --- # 整数划分 > 今天解决 [整数划分(洛谷)](https://www.luogu.com.cn/problem/P4157) ## 思考如下暂时没想好状态转移方程应该如何做，用贪心思想也比较简单。由题目示例数据可得，将n划分为 2a+3b 形式即可得到最大乘积。 (4 + 3 + 3 + 3 = 2 + 2 + 3 + 3 + 3 = 2x2 + 3x3) 通俗来讲就是尽量分为多个2和3相加，并且3尽可能多才能尽可能地大既然知道3要尽可能多就好办了 ### 划分3 > 第一种情况，恰好对3取余为0 ```cpp if ( n % 3 == 0 ) { int b = n / 3; // 累计相乘即可 3的n次方做高精度即可 // ... } ``` > 第二种情况，对3取余为1 其实相当于是将一个3换成2+2 即拿出1个3和余下的1凑成两个2 ```cpp if ( n % 3 == 1 ) { int a = 2; int b = (n - 4) / 3 ; // 同理做高精度 } ``` > 第三种情况，对3取余为2 既然取余剩余2，不妨就多一个单独的2 ```cpp if ( n % 3 == 2 ) { int a = 1; int b = (n - 2) / 3; } ``` 其实总结一下 > 要求整数划分，且积越大，就如同矩形周长划分求面积最大，那么就是正方形最大，即越平均答案越大。 ### 高精度既然我们已经知道应该如何划分，接下来就是计算乘积和输出了。只需要计算a个2和b个3相乘的答案，并且多余100位输出前100位（后面的还是得算，因为需要位数）需要单独开一个进位数组，题目给的限制是不超过**5000**位。 ```cpp // 实际进位可能会超过5000，所以开大一点 int arr[5010]; void multiple(int x) { int amo = 0; for ( int i = 1; i <= arr[0] + 1; ++i ) { arr[i] = arr[i] * x + amo; amo = arr[i] / 10; arr[i] %= 10; } // 最后判断一下首位是否需要进位 if ( arr[arr[0] + 1 ]) arr[0]++; } ``` ### 拼图大概结构列起来之后，直接拼起来即可，以下是完整代码 ```cpp #include using namespace std; // maximum = 31000 int n; int arr[5010]; void multiple(int x) { int amo = 0; for ( int i = 1; i <= arr[0] + 1; ++i ) { arr[i] = arr[i] * x + amo; amo = arr[i] / 10; arr[i] %= 10; } if ( arr[arr[0] + 1 ] ) arr[0]++; } void solve() { if ( n % 3 == 0 ) { for ( int i = 1; i <= n / 3; ++i) { multiple(3); } cout<= max(arr[0] - 99, 1); --i ) { cout<= max(arr[0] - 99, 1); --i ) { cout<= max(arr[0] - 99, 1); --i ) { cout<>n; arr[0] = 1; arr[1] = 1; solve(); return 0; } ``` 总体来说，这道题是一个结论题目。如果刚开始没思路可以先暴力循环，能发现这个结论。重点在高精度。

Contents

personal