#include<iostream> #include<set> #include<vector> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; ll dp[5001][5001]; ll modulo=1000000007; void SubsetSum(vector<ll> &T, int n, ll maxA) { for (int i = 1; i <= maxA; i++) dp[0][i] = 0; dp[0][0]=1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= maxA; j++) { // cout<<"I "<<i<<" J "<<j<<" "; // cout<<"Ti "<<T[i-1]<<"VALUE :"; if (j - T[i - 1]>=T[i-1]-1) { dp[i][j] = dp[i - 1][j]+dp[i - 1][j - T[i - 1]]; } else dp[i][j] = dp[i - 1][j]; //cout<<dp[i][j]<<endl; dp[i][j]%=modulo; } } } int main() { ios_base::sync_with_stdio(0); int n; cin>>n; vector<ll> T(n); ll sume=0; ll maxi=0; for(int i=0 ; i<n ; i++){cin>>T[i]; maxi=max(maxi,T[i]); sume+=T[i];} sort(T.begin(),T.end()); int reached=1; int sum=0; long long result=0; int last=-1; // cout<<SubsetSum(T,n,sume-maxi)<<endl; SubsetSum(T,n,sume); // cout<<endl; // cout<<"Ti "<<T[i]-1<<endl; for(int j=0 ; j<=sume ; j++) { // cout<<"j "<<i<< " j "<<j<<" value "<<dp[i][j]<<endl; result+=dp[n][j]; result%=modulo; } cout<<result%modulo<<endl; 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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include<iostream> #include<set> #include<vector> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; ll dp[5001][5001]; ll modulo=1000000007; void SubsetSum(vector<ll> &T, int n, ll maxA) { for (int i = 1; i <= maxA; i++) dp[0][i] = 0; dp[0][0]=1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= maxA; j++) { // cout<<"I "<<i<<" J "<<j<<" "; // cout<<"Ti "<<T[i-1]<<"VALUE :"; if (j - T[i - 1]>=T[i-1]-1) { dp[i][j] = dp[i - 1][j]+dp[i - 1][j - T[i - 1]]; } else dp[i][j] = dp[i - 1][j]; //cout<<dp[i][j]<<endl; dp[i][j]%=modulo; } } } int main() { ios_base::sync_with_stdio(0); int n; cin>>n; vector<ll> T(n); ll sume=0; ll maxi=0; for(int i=0 ; i<n ; i++){cin>>T[i]; maxi=max(maxi,T[i]); sume+=T[i];} sort(T.begin(),T.end()); int reached=1; int sum=0; long long result=0; int last=-1; // cout<<SubsetSum(T,n,sume-maxi)<<endl; SubsetSum(T,n,sume); // cout<<endl; // cout<<"Ti "<<T[i]-1<<endl; for(int j=0 ; j<=sume ; j++) { // cout<<"j "<<i<< " j "<<j<<" value "<<dp[i][j]<<endl; result+=dp[n][j]; result%=modulo; } cout<<result%modulo<<endl; return 0; } |