#include <bits/stdc++.h> using namespace std; const int mod=1e9+7; int a[5005]; int dp[5005][5005]; int main() { ios_base::sync_with_stdio(0); int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); dp[0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=5001;j++)dp[i][j]=dp[i-1][j]; for(int j=a[i]-1;j<=5001;j++) { dp[i][min(5001,j+a[i])]+=dp[i-1][j]; if(dp[i][min(5001,j+a[i])]>mod)dp[i][min(5001,j+a[i])]-=mod; } } /* for(int i=0;i<=n;i++) { for(int j=0;j<20;j++)cout<<j<<": "<<dp[i][j]<<" "; cout<<endl; }*/ long long res=0; for(int j=1;j<=5001;j++)res+=dp[n][j]; cout<<res%mod<<endl; }
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 34 35 36 | #include <bits/stdc++.h> using namespace std; const int mod=1e9+7; int a[5005]; int dp[5005][5005]; int main() { ios_base::sync_with_stdio(0); int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); dp[0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=5001;j++)dp[i][j]=dp[i-1][j]; for(int j=a[i]-1;j<=5001;j++) { dp[i][min(5001,j+a[i])]+=dp[i-1][j]; if(dp[i][min(5001,j+a[i])]>mod)dp[i][min(5001,j+a[i])]-=mod; } } /* for(int i=0;i<=n;i++) { for(int j=0;j<20;j++)cout<<j<<": "<<dp[i][j]<<" "; cout<<endl; }*/ long long res=0; for(int j=1;j<=5001;j++)res+=dp[n][j]; cout<<res%mod<<endl; } |