CFR 383 D. Antimatter ( DP )

Problem - D - Codeforces

The first line contains an integer n (1 ≤ n ≤ 1000). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000).
The sum a1 + a2 + ... + an will be less than or equal to 10000.

dp[ i ][ j ] : 以第 i 個元素為右界，總和為 j 的選取方案數。

O( N * Sigma( A ) )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
const int MAXS = 10000 + 10;
const int MOD = ( int ) 1e9 + 7;

int N;
int A[ MAXN ];
int _dp[ 2 ][ 4 * MAXS ];
int *dp[ 2 ] = { &_dp[ 0 ][ 2 * MAXS ], &_dp[ 1 ][ 2 * MAXS ] };

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
int ans = 0;
dp[ 0 ][ 0 ] = 1;
for( int i = 0; i < N; ++i ){
for( int j = - MAXS; j <= MAXS; ++j ){
dp[ ~i & 1 ][ j ] = 0;
}
for( int j = - MAXS; j <= MAXS; ++j ){
( dp[ ~i & 1 ][ j + A[ i ] ] += dp[ i & 1 ][ j ] ) %= MOD;
( dp[ ~i & 1 ][ j - A[ i ] ] += dp[ i & 1 ][ j ] ) %= MOD;
}
( ans += dp[ ~i & 1 ][ 0 ] ) %= MOD;
( dp[ ~i & 1 ][ 0 ] += 1 ) %= MOD;
}
cout << ans << endl;
return 0;
}
```