PKU 1837 Balance

PKU

http://poj.org/problem?id=1837

おもりを乗せる場所がｃ個あるはかりに、ｇ個のおもりを乗せたい。
はかりがつりあうようにおもりを乗せる方法が何通りあるかを答えろというような問題。

dp[今まで使った重り][位置と重さの積の総和]=組み合わせの個数
みたいなかんじでやりました。
最大計算量がちょっと危ないかと思いましたが、大丈夫でした。

最初半分全列挙的なものかと思い、解答を思いつくのに苦労しました。

ll dp[23][40000];

int inc[30],ing[30];

main(){
  int c,g;
  cin>>c>>g;
  rep(i,c) cin>>inc[i];
  rep(i,g) cin>>ing[i];

  dp[0][20000]=1;
  rep(i,g)rep(j,40000)if(dp[i][j])
    rep(k,c) dp[i+1][j+inc[k]*ing[i]] += dp[i][j];

  cout<<dp[g][20000]<<endl;
}