#include <bits/stdc++.h> using namespace std; typedef long long int LL; const int MAXN = 5005; const LL M = 1000000007LL; int n; int A[MAXN]; LL dp[2][MAXN + 5]; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> A[i]; sort(A, A+n); dp[0][0] = 1; dp[1][0] = 1; for (int i = 0; i < n; i++) { int x = A[i]; for (int s = x-1; s <= MAXN; s++) dp[1][min(MAXN, s + x)] = (dp[1][min(MAXN, s + x)] + dp[0][s]) % M; for (int s = 0; s <= MAXN; s++) { dp[0][s] = dp[1][s]; } } LL result = 0; for (int i = 1; i <= MAXN; i++) result = (result + dp[0][i]) % M; cout << result << "\n"; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <bits/stdc++.h> using namespace std; typedef long long int LL; const int MAXN = 5005; const LL M = 1000000007LL; int n; int A[MAXN]; LL dp[2][MAXN + 5]; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> A[i]; sort(A, A+n); dp[0][0] = 1; dp[1][0] = 1; for (int i = 0; i < n; i++) { int x = A[i]; for (int s = x-1; s <= MAXN; s++) dp[1][min(MAXN, s + x)] = (dp[1][min(MAXN, s + x)] + dp[0][s]) % M; for (int s = 0; s <= MAXN; s++) { dp[0][s] = dp[1][s]; } } LL result = 0; for (int i = 1; i <= MAXN; i++) result = (result + dp[0][i]) % M; cout << result << "\n"; return 0; } |