【AtCoder】ABC044 C. 高橋君とカード

AtCoderの問題

C: 高橋君とカード / Tak and Cards - AtCoder Beginner Contest 044 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

現在AtCoderの過去問AB(たまにC)解いてます.

難しさ（初心者目線）

・考え方***

・実装**

・面白さ**

問題概要

・数字がN個ある()
・何個か使ってAで割り切れる数を作りたい
・何通りあるか?

方針

・動的計画法
・dp[i][j][k]:=まででj個使ってkを作れる総数

を使うか使わないかの漸化式が考えられる
- 使わない場合は使う個数jとkは変わらない
dp[i+1][j][k] += dp[i][j][k]
- 使う場合は使う個数+1、kはk+x[i]
dp[i+1][j+1][k+x[i]] += dp[i][j][k]

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

ll dp[60][60][3000];
ll N,A;
ll x[60];

int main(){
    cin>>N>>A;
    FOR(i, 0, N) cin>>x[i];
    FOR(i, 0, 60) FOR(j, 0, 60) FOR(k, 0, 3000) dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    FOR(i, 0, N){
        FOR(j, 0, N){
            FOR(k, 0, 3000){
                if(dp[i][j][k]==0) continue;
                //使わない時
                dp[i+1][j][k] += dp[i][j][k];
                //使う時
                dp[i+1][j+1][k+x[i]] += dp[i][j][k];
            }
        }
    }
    ll ans = 0;
    FOR(i, 1, N+1){
        ans += dp[N][i][i*A];
    }
    cout << ans << endl;
}