THPTTD_47 - Tổng fibonaci_k

Xem dạng PDF
Gửi bài giải
Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: fibsum.inp
Output: fibsum.out
Tác giả:
hanhpth
Nguồn bài:
HSG THPT
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, JavaScript, Kotlin, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

Please read the guidelines before commenting.


  • 0
    phucan1402  đã bình luận lúc 4, Tháng 11, 2025, 13:53 
    #include <iostream>
#include <climits>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
using ll = long long;
const int maxn = 1e6;
const ll INF = 1e10;
ll f[12];
ll dp[12][101];
void AC() {
    ll m,k; cin >> m >> k;
    f[0] = f[1] = 1;
    for(int i = 2; i < 12; i++) f[i] = f[i-1] + f[i-2];
    for(int i = 0; i < 12; i++) dp[i][0] = 1;
    for(int i = 1; i < 12; i++) {
        for(int s = 0; s <= m; s++) {
            dp[i][s] = dp[i-1][s];
            for(int t = 1; t <= k; t++) {
                ll val = s - (f[i] * t);
                if(val >= 0) {
                    dp[i][s]+=dp[i-1][val];
                }
            }
        }
    }
    cout << dp[11][m];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("fibsum.inp", "r", stdin);
    freopen("fibsum.out", "w", stdout);
    int t = 1;
    // cin >> t;
    while(t--) {
       AC();
    }
    return 0;
}

  • -2
    Uoao1807  đã bình luận lúc 14, Tháng 12, 2024, 13:10

    cho hỏi cái, tại sao phải thêm dòng 

    freopen("fibsum.inp","r",stdin); 
freopen("fibsum.out","w",stdout);

    vào thì code mới chạy thế? code đúng mà chạy nãy h k được xong vào comment thấy dòng này nên copy vào code mà chạy được luôn


    • 2
      nhatquang1234567890  đã bình luận lúc 11, Tháng 7, 2025, 2:47

      Do đề kêu nhập xuất file á bạn nên phải thêm hai cái này vào vì nếu bạn ko thêm vào nó sẽ là nhập bằng bàn phím và xuất ra màn hình và gây đến lỗi sai không mong muốn (Unexpected EOF in the participant's output)


  • -4
    ______  đã bình luận lúc 26, Tháng 3, 2024, 1:53

    ai chỉ tui dc ko 😭😭😭😭😭


    • 5
      vudinhlong  đã bình luận lúc 26, Tháng 3, 2024, 5:09 ← chỉnh sửa

      1. Xây dựng mảng chứa các số fibo < 100 và mảng đếm có kích thước 100 j đấy để đếm số lầm xh

      2. Quay lui thôi, nhớ là điều kiện xét là lấy các số >= số vừa lấy í (để tránh lặp lại như: 1 1 2 2 và 1 2 1 2 hoặc 2 1 1 2...)

      3. Và nhớ xét cả số lần đã xh (chừng nào còn nhỏ hơn k thì đc xét), xét thì nhớ tăng số lần xh lên 1 đvi

      4. Nếu biết nhánh cận thì có thể giảm số lần đệ quy xuống (if sum + fb[i] <= n)

      => Cơ bản là như thế, bạn có thể tư duy thêm trong lúc làm thêm nhớ <3


      • 0
        ______  đã bình luận lúc 26, Tháng 3, 2024, 15:24

        ily <3