Đề bài:
Thuật toán:
- Thông thường thì ta sẽ có cách giải QHĐ với đpt O(S*n), nhưng vì S lên đến 1e9 nên ta có cách làm như sau:
- Giảm S bằng tờ có giá trị lớn nhất cho đến khi S đủ nhỏ để QHĐ (giảm đến mức nào thì các bạn nên tự thử, trong code mình giảm xuống 100000)
- QHĐ
Code:
#include<bits/stdc++.h> using namespace std; int n,s; int a[101]; int d[100001]; int main() { cin>>n>>s; for (int i=1; i <= n; i++) cin>>a[i]; int mx=0; for (int i=1; i <= n; i++) mx=max(mx,a[i]); int res=0; while (s >= 100001) { res++; s-=mx; } d[0]=0; for (int i=1; i <= s; i++) { d[i]=10000000; for (int j=1; j <= n; j++) if (i >= a[j]) d[i]=min(d[i],d[i-a[j]]+1); } cout<<res+d[s]; return 0; } |
BÌNH LUẬN MỚI