除了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 条评论
-
chenRenning LV 1 @ 2024-5-2 1:07:46
时间复杂度
空间复杂度
#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; }
- 1
