返回题目问答
讨论 / 题目问答/ 帖子详情

怎么优化时间啊QVQ

gually 2024/4/11
除了1，2，4都超时了

**#include**<**bits**/**stdc**++.**h**>
 **using** **namespace** **std**;
 **int** **main**()
 {
 **    **int** **n**,**m**,**x**;**
 **    **scanf**(**"%d%d"**,&**n**,&**m**);**
 **    **int** **dp**[**10005**];**
 **    **for**(**int** **i**=**0**;**i**<**10005**;**i**++)**dp**[**i**]=**10000**;**
 **    **dp**[**0**]=**0**;**
 **    **while**(**n**--)**
 **    **{
 **        **scanf**(**"%d"**,&**x**);**
 **        **dp**[**x**]=**1**;**
 **        **for**(**int** **i**=**1**;**i**<=**m**;**i**++)**
 **        **{
 **            **for**(**int** **j**=**1**;**j**<**i**;**j**++)**
 **            **{
 **                **dp**[**i**]=**min**(**dp**[**i**-**j**]+**dp**[**j**],**dp**[**i**]);**    
             **}**
 **        **}
 **    **
     **}**    
     **printf**(**"%d"**,**dp**[**m**]);
 }
1 回复 0 转发 0 喜欢 69 阅读
回复 (1)
默认 最新
chenRenning 2024/5/2
时间复杂度$O(nm)$

空间复杂度$O(m)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010 , M = 1e4 + 10 ; 

int f[M] ;
// f[i , j] 表示前 i 种纸币凑出金额为 j 的最少数量
int n , m , a[N] ;

int main(int argc, char const *argv[])
{
	cin.tie(nullptr)->ios::sync_with_stdio(false) ;
	cin >> n >> m ;
	for(int i = 1 ; i <= n ; ++ i) cin >> a[i] ;
	memset(f , 0x3f , sizeof f) ; 
	f[0] = 0 ; 
	for(int i = 1 ; i <= n ; ++ i) 
		for(int j = a[i] ; j <= m ; ++ j)
			f[j] = min(f[j] , f[j - a[i]] + 1) ;

	cout << f[m] << '\n' ;
	return 0;
}
0
  1. 兼容模式
  2. © 2024-2028 Dashcoding
  3. 粤ICP备2024204050号-1
  4. Powered by Hydro