2 条题解

  • 3
    @ 2022-12-30 15:29:16
    #include <bits/stdc++.h> 
    #define int unsigned long long
    using namespace std;
    const int Max = 50;
    int a[Max],f[Max][8];
    char c;
    signed main()
    {
    	int n,k;
    	cin>>n>>k;
    	for(int i = 1;i <= n;++ i)
    		cin >> c,a[i] = c - '0';
    	f[1][0] = a[1];
    	for(int i = 1;i <= n;++ i)//枚举到了第几个数字 
    	{
    		for(int j = 0;j <= min(i - 1,k);++ j)//前面有j个乘号 
    		{
    			if(j == 0)
    				f[i][j] = f[i - 1][j] * 10 + a[i];
    			else
    			for(int kk = 1;kk < i;++ kk)//前面j - 1个乘号所在的位置
    			{
    				int ans = 0;
    				for(int z = kk + 1;z <= i;++ z)
    					ans = ans * 10 + a[z];
    				f[i][j] = max(f[i][j],f[kk][j - 1] * ans);
    			}
    		}
    	}
    	cout << f[n][k];
    	return 0;
    }
    
    • 0
      @ 2023-6-1 22:18:11
      #include <cstdio>  
      #include <cstring>  
      #include <algorithm>  
      using namespace std;  
      const int power = 4;
      const int base = 10000; 
      const int MAXL = 106;  
      struct num  
      {  
          int a[MAXL];  
          num() {memset(a,0,sizeof a);} 
          num(char *s)                                  
          {  
              memset(a, 0, sizeof(a));  
              int len = strlen(s);  
              a[0] = (len+power-1) / power;                     
              for (int i=0, t=0, w; i < len ;w *= 10, ++i)          
              {  
                  if (i % power == 0) { w = 1, ++t; }  
                  a[t] += w * (s[i]-'0');  
              }  
          }  
          void add(int k) { if (k || a[0]) a[ ++a[0] ] = k; }  
          void re() { reverse(a+1, a+a[0]+1); } 
          void print()                                      
          {  
              printf("%d", a[ a[0] ]);        
              for (int i = a[0]-1;i > 0;--i)  
              printf("%0*d", power, a[i]);      
              printf("\n");  
          }  
      } dp[46][46][16],cc;  
      bool operator < (const num &p, const num &q)  
      {  
          if (p.a[0] < q.a[0]) return true;  
          if (p.a[0] > q.a[0]) return false;  
          for (int i = p.a[0];i > 0;--i)  
          {  
              if (p.a[i] != q.a[i]) return p.a[i] < q.a[i];  
          }  
          return false;  
      }     
      num operator * (const num &p, const num &q)                    
      {  
          num c;  
          c.a[0] = p.a[0]+q.a[0]-1;  
          for (int i = 1;i <= p.a[0];++i)  
          for (int j = 1;j <= q.a[0];++j)  
          {  
              c.a[i+j-1] += p.a[i]*q.a[j];  
              c.a[i+j] += c.a[i+j-1] / base;  
              c.a[i+j-1] %= base;  
          }  
          if (c.a[ c.a[0]+1 ]) ++c.a[0];  
          return c;
      }  
      int n,k,cnt;
      char fz[MAXL],zh[MAXL];
      int main()  
      {  
      	register int i,j,kk,len,l,sl;
      	scanf("%d%d%s",&n,&k,&fz);
      	for(i=1;i<=n;i++)
      		for(j=1;j<=n;j++)
      		{
      			cnt=0;memset(zh,0,sizeof zh);
      			for(kk=i-1;kk<j;kk++) zh[cnt++]=fz[kk];
      			reverse(zh,zh+strlen(zh));
      			dp[i][j][0]=num(zh);
      		}
      	for(l=1;l<=k;l++)
      		for(len=2;len<=n;len++)
      			for(i=1;i<=n-len+1;i++)
      			{
      				j=i+len-1;
      				for(sl=0;sl<l;sl++)
      				for(kk=i+1;kk<=j;kk++)
      				{
      						cc=dp[i][kk-1][sl]*dp[kk][j][l-sl-1];
      						if(dp[i][j][l]<cc) dp[i][j][l]=cc;
      				}
      			}
      	dp[1][n][k].print();
      	return 0;
      }  
      
      • 1

      [NOIP2000 普及/提高组] 乘积最大

      信息

      ID
      1748
      时间
      1000ms
      内存
      256MiB
      难度
      2
      标签
      递交数
      82
      已通过
      51
      上传者