第五届河南省大学生程序设计竞赛——最强DE 战斗力（大数乘法）

Love The Way You Lie 2022-02-17 10:20 190阅读 0赞

#                                       最强DE 战斗力 #

### 题目链接： ###

[http://nyoj.top/problem/541][http_nyoj.top_problem_541]

## 题目描述: ##

春秋战国时期，赵国地大物博，资源非常丰富，人民安居乐业。但许多国家对它虎视眈眈，准备联合起来对赵国发起一场战争。

显然，面对多个国家的部队去作战，赵国的兵力明显处于劣势。战斗力是决定战争成败的关键因素，一般来说，一支部队的战斗力与部队的兵力成正比。但当把一支部队分成若干个作战队伍时，这个部队的战斗力就会大大的增强。

一支部队的战斗力是可以通过以下两个规则计算出来的：

1.若一支作战队伍的兵力为N，则这支作战队伍的战斗力为N；

2.若将一支部队分为若干个作战队伍，则这支部队的总战斗力为这些作战队伍战斗力的乘积。

比如：一支部队的兵力为5时的战斗力分析如下：

<table style="margin-left:52.4pt;"> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:43pt;"> 情况 </td> 
 <td style="vertical-align:top;width:198pt;"> 作战安排 </td> 
 <td style="vertical-align:top;width:281px;"> 总的战斗力 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:43pt;"> 1 </td> 
 <td style="vertical-align:top;width:198pt;"> 1，1，1，1，1（共分为5个作战队伍） </td> 
 <td style="vertical-align:top;width:281px;"> 1*1*1*1*1=1 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:43pt;"> 2 </td> 
 <td style="vertical-align:top;width:198pt;"> 1，1，1，2&nbsp;&nbsp; （共分为4个作战队伍） </td> 
 <td style="vertical-align:top;width:281px;"> 1*1*1*2=2 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:43pt;"> 3 </td> 
 <td style="vertical-align:top;width:198pt;"> 1，2，2&nbsp;&nbsp;&nbsp;&nbsp; （共分为3个作战队伍） </td> 
 <td style="vertical-align:top;width:281px;"> 1*2*2=4 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:43pt;"> 4 </td> 
 <td style="vertical-align:top;width:198pt;"> 1，1，3&nbsp;&nbsp;&nbsp;&nbsp; （共分为3个作战队伍） </td> 
 <td style="vertical-align:top;width:281px;"> 1*1*3=3 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:43pt;"> 5 </td> 
 <td style="vertical-align:top;width:198pt;"> 2，3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;（共分为2个作战队伍） </td> 
 <td style="vertical-align:top;width:281px;"> 2*3=6 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:43pt;"> 6 </td> 
 <td style="vertical-align:top;width:198pt;"> 1，4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; （共分为2个作战队伍） </td> 
 <td style="vertical-align:top;width:281px;"> 1*4=4 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:43pt;"> 7 </td> 
 <td style="vertical-align:top;width:198pt;"> 5&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; （共分为1个作战队伍） </td> 
 <td style="vertical-align:top;width:281px;"> 5=5 </td> 
 </tr> 
 </tbody> 
</table>

显然，将部队分为2个作战队伍（一个为2，另一个为3），总的战斗力达到最大！

## 输入描述: ##

第一行： N表示有N组测试数据. (2<=N<=5)
 接下来有N行，每行有一个整数Ti 代表赵国部队的兵力. （1<=Ti<=1000） i=1，…N

## 输出描述: ##

对于每一行测试数据，输出占一行，仅一个整数S，表示作战安排的最大战斗力.

## 样例输入: ##

2
    5
    4

## 样例输出: ##

6
    4

### 题意描述： ###

给出一个数字n，将n分解为多个数的和或为本身使得多个数的乘积最大，输出最大结果。

### 解题思路： ###

通过找规律发现当n大于等于5后分解3和（n-3）使得得到的结果最大，因n得范围到1000，大数相乘，定义二维数组存储结果。

### 程序代码： ###

#include<stdio.h>
 #include<string.h>
 int m[1010][1010],len[1010];
 void f(int n,int u,int v)
 {
 	int an1[1010],an2[1010],anx[1010];
 	memset(anx,0,sizeof(anx));
 	int i,j;
 	j=0;
 	for(i=len[u]-1;i>=0;i--)
 		an1[j++]=m[u][i];
 	j=0;
 	for(i=len[v]-1;i>=0;i--)
 		an2[j++]=m[v][i];
 	for(i=0;i<len[u];i++)
 		for(j=0;j<len[v];j++)
 			anx[i+j]+=an1[i]*an2[j];
 	for(i=0;i<1010;i++)
 		if(anx[i]>=10)
 		{
 			anx[i+1]+=anx[i]/10;
 			anx[i]%=10;
 		}
 	len[n]=1010;
 	for(i=1009;i>=0;i--)
 	{
 		if(anx[i]==0)
 			len[n]--;
 		else
 			break;
 	}
 	j=0;
 	for(i=len[n]-1;i>=0;i--)
 		m[n][j++]=anx[i];
 }
 int main()
 {
 	int n,i,t;
 	m[1][0]=1;m[2][0]=2;m[3][0]=3;m[4][0]=4;
 	len[1]=1;len[2]=1;len[3]=1;len[4]=1;
 	for(i=5;i<=1000;i++)
 		f(i,3,i-3);
 	scanf("%d",&t);
 	while(t--)
 	{
 		scanf("%d",&n);
 		for(i=0;i<len[n];i++)
 			printf("%d",m[n][i]);
 		printf("\n");
 	}
 	return 0;
 }

[http_nyoj.top_problem_541]: http://nyoj.top/problem/541