算法至美

用户名：uq_54514514336

访问量：7745

签　名：

等　　级
排　　名	1355
经　　验	2950
参赛次数	0
文章发表	43
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

[STL训练]sort练习-题解（各语言代码）
浏览：139

信息学奥赛一本通T1235-输出前k大的数-题解（各语言代码）
浏览：543

数列有序-题解（Python代码）
浏览：177

你可能喜欢

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

信息学奥赛一本通 T1271-潜水员-题解（各语言代码）

　　作者: 算法至美　　　　发表时间：2022-07-02 16:31:32 浏览：665　|　评论：1　

原题链接：信息学奥赛一本通 T1271-潜水员

和二维01背包问题相反，求最大值变为求最小值
**C++**
```cpp
#include<cstring>
#include<iostream>
using namespace std;
int main(){
	size_t m,n,k,x,y,z,i,j,dp[31][127];
	memset(dp,~0,sizeof(dp));
	cin>>m>>n>>k;
	for(**dp=0;k;--k){
		cin>>x>>y>>z;
		for(i=m;~i;--i)
			for(j=n;~j;--j)
				if(~dp[i][j]){
					size_t&t=dp[min(m,i+x)][min(n,j+y)];
					t=min(t,dp[i][j]+z);
				}
	}
	cout<<dp[m][n];
}
```
**python**
```python
m,n=map(int,input().split())
dp=[[float('inf')]*-~n for _ in range(-~m)]
dp[0][0]=0
for _ in range(int(input())):
	x,y,z=map(int,input().split())
	for i in range(m,-1,-1):
		for j in range(n,-1,-1):
			p,q=min(i+x,m),min(j+y,n)
			if dp[p][q]>dp[i][j]+z:
				dp[p][q]=dp[i][j]+z
print(dp[m][n])
```
**java**
```java
import java.util.Scanner;
import java.util.HashMap;
import java.util.stream.IntStream;
import java.util.stream.Collectors;
import java.util.AbstractMap.SimpleEntry;
public class Main {
	public static void main(String[] args) {
		final Scanner in = new Scanner(System.in);
		final int m = in.nextInt(), n = in.nextInt();
		final HashMap<SimpleEntry<Integer, Integer>, Integer> h = new HashMap<>();
		h.put(new SimpleEntry<>(0, 0), 0);
		IntStream.range(0, in.nextInt()).forEach(o -> {
			final int x = in.nextInt(), y = in.nextInt(), z = in.nextInt();
			h.putAll(h.entrySet().stream().map(i -> {
				final SimpleEntry<Integer, Integer> t = new SimpleEntry<>(Math.min(i.getKey().getKey() + x, m), Math.min(i.getKey().getValue() + y, n));
				return new SimpleEntry<>(t, Math.min(h.getOrDefault(t, Integer.MAX_VALUE), i.getValue() + z));
			}).collect(Collectors.toMap(SimpleEntry::getKey, SimpleEntry::getValue, Math::min)));
		});
		System.out.println(h.get(new SimpleEntry<>(m, n)));
		in.close();
	}
}
```

0.0分

14 人评分

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

　　评论区

瞿肖

一坨屎山......

2023-03-20 15:52:53

算法至美

TA的其他文章

你可能喜欢

人见人爱A+B （C++代码）

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

拆分位数（C++代码）用char简单粗暴，嗯

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

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

信息学奥赛一本通 T1271-潜水员-题解（各语言代码）

评论区

精彩推荐

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

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

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

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

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

计算质因子（C语言代码）

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

分解质因数（C++代码）

买不到的数目（C语言代码）

母牛的故事（C语言代码）

算法至美

TA的其他文章

你可能喜欢

人见人爱A+B （C++代码）

数字整除 （C++代码）——(22行代码)真的只需要两个变量就够了

拆分位数 （C++代码）用char简单粗暴，嗯

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

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

信息学奥赛一本通 T1271-潜水员-题解（各语言代码）

评论区

精彩推荐

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

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

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

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

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

计算质因子 （C语言代码）

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

分解质因数 （C++代码）

买不到的数目 （C语言代码）

母牛的故事 （C语言代码）

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

拆分位数（C++代码）用char简单粗暴，嗯

　　评论区

计算质因子（C语言代码）

分解质因数（C++代码）

买不到的数目（C语言代码）

母牛的故事（C语言代码）