小哈哈

用户名：20180390139

访问量：19724

签　名：

世界上怎么会有那么聪明的人呢？

等　　级
排　　名	216
经　　验	6366
参赛次数	9
文章发表	38
年　　龄	0
在职情况	学生
学　　校	蓝翔挖掘机技校
专　　业	网络工程

　　自我简介：

我是个傻嗨，但是我会努力像个正常人

TA的其他文章

校门外的树（C++代码）------两种解法，复杂点的“并查集”和简单的“数组标记”
浏览：305

蓝桥杯2013年第四届真题-大臣的旅费-题解(C++代码)--------------------重点是这个结论，知道后就很简单了
浏览：397

蓝桥杯2015年第六届真题-赢球票-题解(C++代码)-------------队列的出队入队，很简单的
浏览：342

你可能喜欢

A+B for Input-Output Practice (II) （C语言代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

蓝桥杯算法训练VIP-乘积最大-题解(C语言代码)------------动态规划简单描述

　　作者: 小哈哈　　　　发表时间：2019-10-05 23:18:01 浏览：1037　|　评论：1　

原题链接：蓝桥杯算法训练VIP-乘积最大

这道题可以用动态规划，也可以用dfs,这里用动态规划来解题
首先要确定状态，也就是你想用dp[i][j]表示什么
这里就用来表示：在长度为i的字符串里插入j个乘号，所得的乘积最大值为
dp[i][j],那么最终的答案就是dp[n][m]了
接下来我们要写状态转移方程：dp[i][j]=max{dp[k][j-1]*sum}  k<i
这里的dp[k][j-1]表示长度为k的字符串，插入j-1个乘号时它的乘积最大值为
dp[k][j-1]而sum表示k到i这段字符串表示的数字，也就是剩下的那部分字符串的大小
神马意思呢：比如12345这个字符串插入两个乘号的最大乘积，也就是dp[4][2]为多少，那你要考虑,max{   dp[1][1]    ,dp[2][1]    ,dp[3][1]  dp[4][1]}

这里的dp[1][1]*sum表示   dp[1][1]乘2345，这里sum=2345
这里的dp[2][1]*sum表示 dp[2][1]乘345，这里sum=345
dp[3][1]*sum表示 dp[3][1]乘45，这里sum=45
dp[4][1]*sum表示dp[4][1]乘5，这里sum=5

#include<stdio.h>
    #define N 100
    int n,m,dp[N][N]={0},a[N]={0};
    int max(int a,int b){
    	return a>b ? a:b;
    }
    int fun(int start,int end){
    
    	int i,sum=0;
    	for(i=start;i<=end;i++){
    		sum=sum*10+a[i];
    	}
    	return sum;
    }
    int main(){
    	int i,j,k,mid;
    	char s[N];
    	scanf("%d%d",&n,&m);
    	scanf("%s",s);
    	i=0;
    	while(s[i]!='\0'){
    		a[i+1]=s[i]-'0'+0;
    		i++;
    	};
    	for(i=0;i<=n;i++){
    		dp[i][0]=fun(1,i);
    	}
    	for(i=1;i<=n;i++){
    		for(j=1;j<=m&&i-1>=j;j++){
    			for(k=1;k<i;k++){
    				dp[i][j]=max(dp[i][j],dp[k][j-1]*fun(k+1,i));
    				
    			}
    				
    		}
    
    	}
    	printf("%d\n",dp[n][m]);
    	return 0;
    }

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

robotoj

这个数据竟然水到int 都不会爆//

2020-11-12 11:02:56

小哈哈

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

求圆的面积（C++代码）这里推荐使用宏定义

Lucky Word （C++代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

蓝桥杯算法训练VIP-乘积最大-题解(C语言代码)------------动态规划简单描述

评论区

精彩推荐

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

C语言训练-排序问题<1> （C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

简单的a+b （C语言代码）

众数问题（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

【偶数求和】（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-分段函数（C语言代码）

小哈哈

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

求圆的面积 （C++代码）这里推荐使用宏定义

Lucky Word （C++代码）

【明明的随机数】 （C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

蓝桥杯算法训练VIP-乘积最大-题解(C语言代码)------------动态规划简单描述

评论区

精彩推荐

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

C语言训练-排序问题<1> （C语言代码）

数组输出 （C语言代码）--此题的题目描述有问题

简单的a+b （C语言代码）

众数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

【偶数求和】 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-分段函数 （C语言代码）

求圆的面积（C++代码）这里推荐使用宏定义

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

　　评论区

C二级辅导-分段函数（C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

众数问题（C语言代码）

【偶数求和】（C语言代码）

C二级辅导-分段函数（C语言代码）