第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-116 最大的算式

#include<stdio.h>
#include<stdlib.h>
long long int jc(int n)
{
  long long int sum=1;
  while(n)
  {
    sum*=n;
    n--;
  }
  return sum;
}
int main()
{
  int n,k;
  short i,j;
  int *p;
  int *q; 
  int *t_i;
  long long Mmax=0; 
  int times;
  int x=0;
  scanf("%d%d",&n,&k);
  p=(int *)malloc(n*sizeof(int));
  q=(int *)malloc((k+1)*sizeof(int));
  t_i=(int *)malloc((k+1)*sizeof(int));
  for(i=0;i<n;i++)
  scanf("%d",p+i);
  
  times=jc(n-1)/(jc(k)*jc(n-1-k));
  for(i=0;i<k+1;i++)
  {
    t_i[i]=1;
   } 
  for(i=1;i<=times;i++)     //times次排列组合 
  {
    int sum_i=0;
    int s=0;
    for(j=0;j<k;j++)      //求最后一个组合数； 
    {
      sum_i+=t_i[j];
    }
    t_i[j]=n-sum_i;
    for(j=0;j<k+1;j++)      //K+1个组合 
    {
      q[j]=0;
      int m;
      for(m=0;m<t_i[j];m++) //每个组合的和； 
      {
        q[j]+=p[s++];
      }    
    }
    long long max=1;
    for(j=0;j<k+1;j++)
    {
      max*=q[j];
     } 
     if(max>Mmax)
     Mmax=max;
    for(j=k-1;j>=0;j--)     //每个组合的个数； 
    {
      if((t_i[j]+1)<=(n-k)&&sum_i+1<n)
      {
        t_i[j]++;
        break;
      }
      else
      {
        sum_i-=(t_i[j]-1);
        t_i[j]=1;
      }
    }
  
    
  }
  printf("%lld\n",Mmax);
  free(q);
  free(t_i);
  free(p);
  return 0;
}

#include <iostream>
using namespace std;
#define MAXN 15
typedef unsigned long long  ULL;
int N, K, All; // 数字总数, 乘号总数, 符号总数 
int dp[MAXN][MAXN];
bool Symbol[MAXN-1];
ULL MaxValue = 0;
void Dfs( int deep, int begin )
{
  if( deep == K )
  {
    ULL sum = 1;
    for( int i = 0,start=0; i < N; ++i )
    {
      start = i;
      while( Symbol[i] == false && i < All )
        ++i;
      sum *= dp[start][i];
    }
    if( sum > MaxValue )
      MaxValue = sum;
  }
  else
  {
    for( int i = begin; i < All; ++i )
      if( !Symbol[i] )
      {
        Symbol[i] = true;
        Dfs(deep+1, i+1);
        Symbol[i] = false;
      }
  }
}
int main(int argc, char** argv) {
  cin >> N >> K;
  All = N - 1; 
  for( int i = 0; i < All; ++i) Symbol[i]=false;
  for(int i = 0; i < N; ++i ) cin >> dp[i][i];  
  for( int i = 0; i < N; ++i )
    for( int j = i+1; j < N; ++j )
      dp[i][j] = dp[i][j-1] + dp[j][j];
  Dfs(0,0);
  cout << MaxValue;
  return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);
        
        long[][] dp = new long[n+1][k+1];    //dp[i][j]表示前i个数中有j个乘号时，所得最大值
        int[] sum = new int[n+1];        //前i个数之和
        
        str = br.readLine().split(" ");
        for(int i = 1; i <= n; i++) {
            sum[i] =  sum[i-1] + Integer.parseInt(str[i-1]);
        }
        
        //没有乘号的情况，即连加的情况
        for(int i = 1; i <= n; i++) {
            dp[i][0] = sum[i];
        }
        //动态规划
        for(int i = 2; i <= n; i++) {                    //前i个数
            for(int j = 1; j <= i-1 && j <= k; j++) {    //乘号的个数
                for(int p = 2; p <= i; p++) {            //乘号的位置
                    dp[i][j] = max(dp[i][j], dp[p-1][j-1] * (sum[i] - sum[p-1]));//求前i个数有j个乘号时的最大值
                }
            }
        }
        
        System.out.println(dp[n][k]);
    }
    private static long max(long a, long b) {
        return a>b?a:b;
    }
}

s = list(map(int, input().split()))
n, k = s[0], s[1]
num = [int(n) for n in input().split()]    #数组
temp = num[0]
# dp = np.zeros([n+1,k+1], dtype = np.int)
dp = [[0 for i in range(k+1)] for j in range(n+1)]
dp[1][0] = num[0]
for i in range(1, n):
    temp += num[i]
    dp[i+1][0] = temp
if k == 0:
    print(dp[n][k])
else:
    # 按照列遍历
    for j in range(1, k + 1):
        # 按照行
        for i in range(2, n + 1):
            if i > j:
                for p in range(1, i):
                    dp[i][j] = max(dp[i][j], dp[p][j - 1] * (dp[i][0] - dp[p][0]))
    print(dp[n][k])