当前位置:网站首页>[oiclass] maximum formula
[oiclass] maximum formula
2022-07-06 14:48:00 【Liujincheng LJC】
problem : The biggest formula
Title Description
The subject is very simple , give N A digital , Don't change their relative position , Add... In the middle K A multiplication sign and N-K-1 Plus sign ,( Put in parentheses ) Maximize the final result . Because the multiply sign and the plus sign are N-1 A the , So there's just a sign between every two adjacent numbers . for example :
N=5, K=2,5 The numbers are 1、2、3、4、5, Can add :
1*2*(3+4+5)=24
1*(2+3)*(4+5)=45
(1*2+3)*(4+5)=45
...
Input
The input file has two lines , The first line is two integers separated by spaces , Express N and K, among (2<=N<=15, 0<=K<=N-1). Second behavior N A number separated by a space ( Each number is in 0 To 9 Between ).
Output
The output file contains only one integer on one line , Represents the maximum result required
The final result <=maxlongint
Examples
#1
Input
5 2
1 2 3 4 5
Output
120
Previous ideas
Think f[i][j][k] It should be defined like this :
set up f[i][j][k] For in [i , j] Within the interval of k A multiple sign
State transition equation :
f[i][j][k] = max4(f[i+1][j][k]+a[i],f[i][j-1][k]+a[j],
f[i+1][j][k-1]*a[i],f[i][j-1][k-1]*a[j]);
Then the wrong code should be like this :
#include<bits/stdc++.h>
using namespace std;
const int N = 101;
int n,m,a[N],f[N][N][N*11];
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=n;i>0;i--){
for(int j=i;j<=n;j++){
for(int k=0;k<=m;k++){
f[i][j][k] = max(f[i+1][j][k]+a[i],
max(f[i+1][j][k-1]*a[i],
max(f[i][j-1][k]+a[j],
f[i][j-1][k-1]*a[j])));
}
}
}
cout << f[1][n][m] << endl;
}
/************************************************************** Language: C++ Result: Wrong answer 50 ****************************************************************/
got 50 branch , Later, I found several error examples and found them by comparison :
This section can be cut from more than two sides , It can also be cut from any position in the middle , If you cycle the middle line , Then the number of multiplication signs can be more or less . At this time f[i][j][k] The initialization of will become -INF This is running max Function to find the optimal solution
On AC Code :
#include<bits/stdc++.h>
#define INF 2147483647
using namespace std;
const int N = 110;
int n,m,a[N],f[N][N][N];
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];}
for(int i=1;i<=n;i++){
f[i][i][0] = a[i];
}
for(int i=n;i>0;i--){
for(int j=i+1;j<=n;j++){
for(int k=0;k<=min(j-i,m);k++){
if(m-(n-(j-i))>=k){
f[i][j][k]=-INF;
continue;
}
for(int z=i;z<j;z++){
for(int y=0;y<=k;y++){
f[i][j][k] = max(f[i][j][k],f[i][z][y]+f[z+1][j][k-y]);
if(y==0){
f[i][j][k] = max(f[i][z][y]*f[z+1][j][k-y-1],
f[i][j][k]);
}
else{
f[i][j][k] = max(f[i][z][y-1]*f[z+1][j][k-y],
f[i][j][k]);
}
}
}
}
}
}
// cout << f[3][5][1] <<endl;
cout << f[1][n][m] << endl;
}
/************************************************************** Language: C++ Result: correct 100 Time:0 ms Memory:6912 kb ****************************************************************/
边栏推荐
- 数字电路基础(五)算术运算电路
- Cadence physical library lef file syntax learning [continuous update]
- What is the transaction of MySQL? What is dirty reading and what is unreal reading? Not repeatable?
- Fundamentals of digital circuit (IV) data distributor, data selector and numerical comparator
- 《统计学》第八版贾俊平第四章总结及课后习题答案
- Proceedingjoinpoint API use
- {1,2,3,2,5} duplicate checking problem
- MySQL中什么是索引?常用的索引有哪些种类?索引在什么情况下会失效?
- 【指针】删除字符串s中的所有空格
- Statistics 8th Edition Jia Junping Chapter 3 after class exercises and answer summary
猜你喜欢
servlet中 servlet context与 session与 request三个对象的常用方法和存放数据的作用域。
Statistics 8th Edition Jia Junping Chapter IX summary of knowledge points of classified data analysis and answers to exercises after class
Don't you even look at such a detailed and comprehensive written software test question?
Fundamentals of digital circuits (I) number system and code system
Statistics 8th Edition Jia Junping Chapter XIII Summary of knowledge points of time series analysis and prediction and answers to exercises after class
Statistics 8th Edition Jia Junping Chapter 2 after class exercises and answer summary
“人生若只如初见”——RISC-V
Lintcode logo queries the two nearest saplings
Intranet information collection of Intranet penetration (4)
Captcha killer verification code identification plug-in
随机推荐
内网渗透之内网信息收集(三)
Statistics 8th Edition Jia Junping Chapter 2 after class exercises and answer summary
Captcha killer verification code identification plug-in
What is an index in MySQL? What kinds of indexes are commonly used? Under what circumstances will the index fail?
【指针】数组逆序重新存放后并输出
5 minutes to master machine learning iris logical regression classification
. Net6: develop modern 3D industrial software based on WPF (2)
Overview of LNMP architecture and construction of related services
The salary of testers is polarized. How to become an automated test with a monthly salary of 20K?
Matplotlib绘图快速入门
Zhejiang University Edition "C language programming experiment and exercise guide (3rd Edition)" topic set
1. Payment system
《统计学》第八版贾俊平第六章统计量及抽样分布知识点总结及课后习题答案
Statistics, 8th Edition, Jia Junping, Chapter 6 Summary of knowledge points of statistics and sampling distribution and answers to exercises after class
《统计学》第八版贾俊平第二章课后习题及答案总结
Function: find the root of the equation by Newton iterative method
《统计学》第八版贾俊平第十四章指数知识点总结及课后习题答案
浙大版《C语言程序设计实验与习题指导(第3版)》题目集
Wang Shuang's detailed learning notes of assembly language II: registers
ES全文索引