14 solutions

  • 0
    @ 2024-6-9 19:43:05

    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;
    }
    

    Information

    ID
    106
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    6
    Tags
    # Submissions
    513
    Accepted
    165
    Uploaded By