首页 > 代码库 > 最强DE 战斗力(nyoj541)

最强DE 战斗力(nyoj541)

2024-07-05 07:31:46   222人阅读

题意不用解释了就是求积最大，但考虑到什么时候积会是最大

a1+a2+.....an=M;

a1*a2*.....an=max;

要求当a1+...an=n 时求他们所有值得最大乘积当且仅当

a1=a2=a3=...=an

所以原式化简为

n*a=M;

max=a^n;带入解得最大的取值为3；

所以取值都是3的倍数，接下来就是个大数处理问题，最大的值会有pow(3,32)*4,所以用数组储存，开一个200的数组足够了！

代码:

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<string.h>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<vector>
 8 #include<cstring>
 9 #include<stack>
10 #include<stdlib.h>
11 #include<ctype.h>
12 using namespace std;
13 #define MAXN 1300
14 #define inf 100000
15 
16 int dp[230];
17 void acc(int x)
18 {
19     int i,t;
20     for( i=t=0;i<200;i++)
21     {
22         t=dp[i]*x+t;
23         dp[i]=t%10;
24         t=t/10;
25     }
26 }
27 int main()
28 {
29     int t,n,a;
30     cin>>t;
31     while(t--)
32     {
33         int i,j;
34         memset(dp,0,sizeof dp);
35         cin>>n;
36         a=n/3;
37         if(n%3==1)a--;//如果取余得1，那最大值就要包含一个4
38         dp[0]=1;
39         for( i=0;i<a;i++)
40             acc(3);//a个3相乘
41         if(n%3==1)acc(4);
42         else if(n%3==2)acc(2);
43         j=200;
44         while(!dp[j])
45         {
46             j--;
47         }
48         for( i=j;i>0;i--)
49             cout<<dp[i];
50         cout<<dp[0]<<endl;
51     }
52 }
View Code

 

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      


联系
我们