SEQMODK - Dãy con có tổng chia hết cho K
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho một dãy gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_n~ và số nguyên dương ~K~. Hãy tìm dãy con gồm nhiều phần tử nhất của dãy đã cho sao cho tổng các phần tử của dãy con này chia hết cho ~K~.
Input
- Dòng đầu ghi hai số nguyên dương ~N~ và ~K~ cách nhau bởi một khoảng trắng;
- Dòng thứ hai ghi ~N~ số ~a_1, a_2, ..., a_n~, mỗi số cách nhau bởi một khoảng trắng.
Giới hạn:
- ~1 ≤ N ≤ 1000; 1 ≤ K ≤ 100; |a_i|≤ 10^9~
Output
- Ghi ra một số nguyên duy nhất là số phần tử của dãy dài nhất tìm được.
Sample
Input #1
10 3
3 2 5 7 9 6 12 7 11 15
Output #1
9
Hint
- Dãy dài nhất có ~9~ phần tử là ~3, 5, 7, 9, 6, 12, 7, 11, 15~
Problem source: Chuyên Sơn La Online Judge
Bình luận
include <bits/stdc++.h>
define debug(n) cout << #n << " = " << n << "\n"
using namespace std;
const int maxN = 57;
int N, K; int Sub(int x, int y) { int tmp = (x - y) % K; if (tmp >= 0) return tmp; return tmp + K; }
void solve() { cin >> N >> K; vector<int> a(N + 1); for (int i = 0; i < N; i++) { cin >> a[i]; a[i] = a[i] % K; } int dp[N][K]; memset(dp, 1, sizeof dp); for (int i = 1; i < K; i++) dp[0][i] = -1e9 - 7; dp[0][0] = 1; for (int i = 1; i < N; i++) { for (int j = 0; j <= K - 1; j++) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][Sub(j, a[i - 1])] + 1); } } cout << dp[N - 1][0] << "\n"; }
int main() { iosbase::syncwith_stdio(0); cin.tie(0);
} giúp đỡ mn nha
tham khảo thôi đừng copy-paste nha
e làm cứ bị sai 3 test ạ :(( mọi người ai bị v cho e cách fix với ạ