Java实现 第十一届蓝桥杯——超级胶水(渴望有题目的大佬能给小编提供一下题目,讨论群:99979568)
2024-09-06 00:04:32
PS:
好久没写过算法题了,总感觉自己写的思路没问题,但是结果就是不对,希望哪位大佬有时间能给找找问题
超级胶水
小明有n颗石子,按顺序摆成一排,他准备用胶水将这些石子黏在一起。
梅克什字有自己的重量,如果将两颗石子黏在一起,重量就是两个石子重量之和
为了粘贴牢固,该题认为两个石子粘连需要的胶水为两个石子的重量乘积。
每次只能合并相邻的两颗石子,并将合成的石子放在原来的位置,用最少的交水黏在一起,
请帮助小明计算最少需要多少胶水
输入:
n:石子的数量
n个整数w1,w2……wn,表示每颗石子的重量
输出:
最少的胶水数量
package 第十一届蓝桥杯; import java.util.Scanner; public class 超级胶水 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[1010];
int[][] temp = new int[1010][1010];
int[][] dp = new int[1010][1010];
int[][] jiaoshui = new int[1010][1010];
// int[][] jiao = new int[1010][1010];
// int[][] zong = new int[1010][1010];
for (int i=1; i<=n; i++) {
a[i] = in.nextInt();
temp[i][i] = a[i];
// jiao[i][i]=a[i];
dp[i][i]=a[i];
}
for (int i=1; i<n; i++) {
for(int j=i+1; j<=n; j++) {
temp[i][j] = temp[i][j-1] + a[j];
// jiao[i][j]=jiao[i][j-1]*a[i];
}
}
for (int r=2; r<=n; r++) {
for (int i=1; i<=n-r+1; i++) {
int j=i+r-1;
jiaoshui[i][j] = Integer.MAX_VALUE;
dp[i][j] = Integer.MAX_VALUE;
int temp1 = 0;
for (int k=i; k<j; k++) {
if(jiaoshui[i][j] > dp[i][k] * dp[k+1][j])
temp1=k;
dp[i][j] = dp[i][k] + dp[k+1][j]; jiaoshui[i][j] = dp[i][k] * dp[k+1][j];
}
jiaoshui[i][j]+=jiaoshui[i][temp1];
jiaoshui[i][j]+=jiaoshui[temp1+1][j];
// dp[i][j] += temp[i][j];
// jiaoshui[i][j]*=jiao[i][j];
}
}
// System.out.println(dp[1][n]);
System.out.println(jiaoshui[1][n]);
// System.out.println(zong[1][n]);
}
}
最新文章
- js学习之变量、作用域和内存问题
- Maven部署构件至远程仓库
- noi 1.5 43:质因数分解
- ORA-02287: 此处不允许序号
- Docker(linux container) 所依赖的底层技术
- MVC,布局页面
- 老毛桃安装Win8(哪里不会点哪里,so easy)
- svn的管理与维护要点—纯手工编写
- 一个基于Myeclipse开发的Java打地鼠小游戏(Appletcation)
- angularjs的事件 $broadcast and $emit and $on
- js 获取url中的查询字符串
- linux下编译运行驱动
- XML 新手入门基础知识(复制,留着自己看)
- CentOS7配置更新国内yum源
- 在Linux机器上安装telnet命令
- python3解析库BeautifulSoup4
- Bootstrap3基础 img-responsive 响应式图片
- Java 使用jdk自带的wsimport命令生成webservice客户端代码
- PHP 写文件的例子
- 源项目 ->; fork ->; 本地 (如何把源项目的代码合并到本地然后推送给fork)