Information
- ID
- 106
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 6
- Tags
- # Submissions
- 559
- Accepted
- 176
- Uploaded By
dp+前缀和,dp[i][j]代表使用 j 个正整数组成 i 的方案数,最终输出dp[2021][5]即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[2022][6];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
for (int i = 1; i <= 2021; ++ i) {
dp[i][1] = 1;
}
for (int j = 2; j <= 5; j++) {
for (int i = 1; i <= 2021; i++) {
long long sum = 0;
for (int x = 1; x <= i - j + 1; x++) {
sum += dp[i - x][j - 1];
}
dp[i][j] = sum;
}
}
cout << dp[2021][5];
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.