4 条题解
-
0wangguanding1 LV 8 @ 2023-8-20 14:34:35
#include<bits/stdc++.h> using namespace std; int w[100001],v[100001],dp[100001]; int main(){ int n,m; cin>>m>>n; for(int i=1;i<=n;i++){ cin>>w[i]; } for(int i=1;i<=n;i++){ for(int j=m;j>=w[i];j--){ dp[j]=max(dp[j],dp[j-w[i]]+w[i]); } } cout<<m-dp[m]; return 0; }
-
02023-5-26 21:51:39@
/***************** 备注: *****************/ #include <iostream> #include <iomanip> #include <cmath> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; #define LL long long #define MAXM 3010 #define MAXN 3010 const int N =1e5+10; const int INF =0x3f3f3f3f; int maxx = -INF,n,minn = INF,v; int a[N]; void dfs(int step,int sum) { if (sum <= v) maxx = max(maxx,sum); if (sum > v or step > n) return; dfs(step+1,sum+a[step]); dfs(step+1,sum); } int main(){ cin >> v >> n; for (int i = 1;i<=n;i++) { cin >> a[i]; } dfs(1,0); cout << v - maxx; return 0; }
-
02022-10-26 22:37:13@
#include<bits/stdc++.h> using namespace std; int q,a[100001],b[100001]; int main(){ int w; cin>>w>>q; int i, j; for (i = 0; i < q; i++){ cin>>a[i]; } for (i = 0; i < q; i++){ for (j = w; j >= a[i]; j--) b[j] = max(b[j], b[j - a[i]] + a[i]); } cout<<w - b[w]; return 0; }
-
02022-10-5 9:50:51@
#include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <cstdio> #include <string> #include <iomanip> #include <queue> #include <stack> #include <list> #include <map> #include <vector> #include <fstream> using namespace std; const int N = 1e5+10; const int INF = 0x3f3f3f3f; int maxx = -INF,n,minn = INF,v; int a[N]; void dfs(int step,int sum){ if (sum <= v) maxx = max(maxx,sum); if (sum > v or step > n) return; dfs(step+1,sum+a[step]); dfs(step+1,sum); } int main(){ cin >> v >> n; for (int i = 1;i<=n;i++){ cin >> a[i]; } dfs(1,0); cout << v - maxx; return 0; }
- 1
信息
- ID
- 1300
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 290
- 已通过
- 76
- 上传者