CFR 383 D. Antimatter ( DP )

Problem - D - Codeforces

題意：
給一個 N 個正整數組成的 A 數列。可以選一個連續區間，並決定每個數值分別的正負號，但其總和必須為 0 才合法。問有幾種合法的選取方式，選取方式相異若左界或右界不同，或任意一個元素分配到的正負號不同。輸出方案數對 1e9 + 7 取模。注意 A 元素總和不會超過 10000。

資料規模：
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 的選取方案數。
為了要讓每個元素都有當左界的機會，所有 dp[ i ][ A[ i ] ] 和 dp[ i ][ - A[ i ] ] 要在適當的時候初始為 1。
答案顯然是 Sigma{ dp[ i ][ 0 ] }。
這裡用可存取負數的陣列實作。

時間 / 空間複雜度：
O( N * Sigma( A ) )

注意：
當使用的是可存取負數的這種陣列，sizeof 會失效，memset 就會爛掉。
所以，不要用 memset。

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