整数划分

今天解决 整数划分(洛谷)

思考如下

暂时没想好状态转移方程应该如何做，用贪心思想也比较简单。

由题目示例数据可得，将n划分为 2a+3b 形式即可得到最大乘积。

(4 + 3 + 3 + 3 = 2 + 2 + 3 + 3 + 3 = 2x2 + 3x3)

通俗来讲就是尽量分为多个2和3相加，并且3尽可能多才能尽可能地大

既然知道3要尽可能多就好办了

划分3

第一种情况，恰好对3取余为0

if ( n % 3 == 0 ) {
  int b = n / 3;

  // 累计相乘即可 3的n次方 做高精度即可
  // ...
}

第二种情况，对3取余为1

其实相当于是将一个3换成2+2

即拿出1个3和余下的1凑成两个2

if ( n % 3 == 1 ) {
  int a = 2;
  int b = (n - 4) / 3 ;

  // 同理做高精度
}

第三种情况，对3取余为2

既然取余剩余2，不妨就多一个单独的2

if ( n % 3 == 2 ) {
  int a = 1;
  int b = (n - 2) / 3;
}

其实总结一下

要求整数划分，且积越大，就如同矩形周长划分求面积最大，那么就是正方形最大，即越平均答案越大。

高精度

既然我们已经知道应该如何划分，接下来就是计算乘积和输出了。

只需要计算a个2和b个3相乘的答案，并且多余100位输出前100位（后面的还是得算，因为需要位数）

需要单独开一个进位数组，题目给的限制是不超过5000位。

// 实际进位可能会超过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]++;
}

拼图

大概结构列起来之后，直接拼起来即可，以下是完整代码

#include <bits/stdc++.h>

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<<arr[0]<<endl;
  
  for( int i = arr[0]; i >= max(arr[0] - 99, 1); --i ) {
   cout<<arr[i]; 
  };
 }
 
 if(n % 3 == 1){
  for( int i = 1; i <= n / 3 - 1; ++i ) {
   multiple(3); 
  }
  
  multiple(4);
  
  cout<<arr[0]<<endl;
  for( int i = arr[0]; i >= max(arr[0] - 99, 1); --i ) {
   cout<<arr[i];
  }
 }
 
 if( n % 3 == 2 ) {
  for( int i = 1; i <= n / 3; ++i ) {
   multiple(3); 
  }
  
  multiple(2);
  
  cout<<arr[0]<<endl;
  
  for( int i = arr[0]; i >= max(arr[0] - 99, 1); --i ) {
   cout<<arr[i]; 
  }
 }
}

int main() {
 cin>>n;
 
 arr[0] = 1;
 arr[1] = 1;
 
 solve();
 
 return 0;
} 

总体来说，这道题是一个结论题目。如果刚开始没思路可以先暴力循环，能发现这个结论。重点在高精度。