第十四届蓝桥杯集训——练习解题阶段(无序阶段)-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])