Hướng dẫn giải của Bedao Mini Contest 16 - NUMBER


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Gọi hàm ~dp(pos,cnt,last)~ là số lượng số dãy con gồm ~cnt~ phần tử khi xét đến vị trí ~pos~ và chữ số tận cùng của số đang tạo là ~last~.

Vì đứng ở vị trí ~pos~ ta có thể thêm chữ số ~a[pos]~ vào xâu đang tạo để tạo ra xâu con mới hoặc bỏ qua ~a[pos]~ nên ta có công thức quy hoach động như sau:

  • ~dp(pos,cnt,last)~ = ~dp(pos+1,cnt+1,a[pos]\%2)~ + ~dp(pos+1,cnt,last)~.
  • Nếu ~a[pos]~ là số ~0~ ta cần chú ý xem ~cnt~ đang xét có khác ~0~ hay không.(Vì nếu ~cnt = 0~ ta không thể bỏ số 0 vào dãy con được)

Code mẫu

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i ++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i --)
using namespace std;
const long long INF = 1e18;
const long long N = 2e5 + 5;
const long long MOD = 1e9 + 7;
ll n, a[N], dp[N][40], k;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n;
    rep(i, 1, n) cin >> a[i];
    cin >> k;
    if (k == 1) {
        ll ans = 0;
        rep(i, 1, n) ans += 1 - a[i] % 2;
        cout << ans << '\n';
        return 0;
    }

    ll ans = 0;

    rrep(i, n, 1) {

        rep(j, 1, k) dp[i][j] = dp[i + 1][j];
        if (a[i] % 2 == 0) dp[i][1] ++;
        rep(j, 2, k - 1)
            dp[i][j] += dp[i + 1][j - 1];
        if (a[i]) dp[i][k] += dp[i + 1][k - 1];
        rep(j, 1, k) dp[i][j] %= MOD;
    }

    cout << dp[1][k];

    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.