第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-116 最大的算式
目录
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-116 最大的算式
前言
最大的算式
C语言
C 语言
Java语言
Python语言
总结
第六届——第十三届省赛题解
第六届——第十二届国赛题解
前言
这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。
最大的算式
资源限制
内存限制：256.0MB C/C 时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如： N=5，K=2，5个数字分别为1、2、3、4、5，可以加成： 1*2*(3 4 5)=24 1*(2 3)*(4 5)=45 (1*2 3)*(4 5)=45 ……
输入格式
输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<=N<=15, 0<=K<=N-1）。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。
输出格式
输出文件仅一行包含一个整数，表示要求的最大的结果
样例输入
5 2 1 2 3 4 5
样例输出
120
样例说明
(1 2 3)*4*5=120
题解：
C语言
代码语言：javascript复制#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("%lldn",Mmax);
free(q);
free(t_i);
free(p);
return 0;
}C 语言
代码语言：javascript复制#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;
}Java语言
在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。
代码语言：javascript复制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;
}
}Python语言
相对简洁，但是需要对Python的一些语法很了解，特别是列表推导式的熟悉。
代码语言：javascript复制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])总结
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
第六届——第十三届省赛题解
所有的题目都做了讲解，最难的有配套的视频，视频提供者是【2020级的弓家宜】先生。
第六届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123284163 |
|---|---|
第七届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123285783 |
第八届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123302677 |
第九届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123303285 |
第十届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123319090 |
第十一届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/123320205 |
第十二届Java省赛C组第一套 | https://laoshifu.blog.csdn.net/article/details/123413141 |
第十二届Java省赛C组第二套 | https://laoshifu.blog.csdn.net/article/details/123413271 |
第十三届Java省赛C组 | https://laoshifu.blog.csdn.net/article/details/128891276 |
第六届——第十二届国赛题解
所有题目均有题解，部分第10题非最优解，至少跑20%数据。
第六届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123440705 |
|---|---|
第七届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123442982 |
第八届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123443626 |
第九届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123443908 |
第十届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123444946 |
第十一届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123445601 |
第十二届Java国赛C组 | https://laoshifu.blog.csdn.net/article/details/123446589 |
