結果
問題 | No.196 典型DP (1) |
ユーザー | airis |
提出日時 | 2015-05-10 15:16:53 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 1,492 bytes |
コンパイル時間 | 715 ms |
コンパイル使用メモリ | 80,232 KB |
実行使用メモリ | 35,424 KB |
最終ジャッジ日時 | 2023-09-19 09:42:33 |
合計ジャッジ時間 | 3,914 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
35,164 KB |
testcase_01 | AC | 26 ms
34,888 KB |
testcase_02 | AC | 26 ms
34,948 KB |
testcase_03 | AC | 26 ms
34,888 KB |
testcase_04 | AC | 27 ms
35,016 KB |
testcase_05 | AC | 26 ms
34,892 KB |
testcase_06 | AC | 27 ms
34,944 KB |
testcase_07 | AC | 26 ms
34,876 KB |
testcase_08 | AC | 26 ms
34,884 KB |
testcase_09 | AC | 25 ms
34,876 KB |
testcase_10 | AC | 26 ms
35,172 KB |
testcase_11 | AC | 26 ms
34,892 KB |
testcase_12 | AC | 26 ms
34,872 KB |
testcase_13 | AC | 27 ms
34,948 KB |
testcase_14 | AC | 26 ms
34,892 KB |
testcase_15 | AC | 27 ms
34,896 KB |
testcase_16 | AC | 29 ms
34,896 KB |
testcase_17 | AC | 31 ms
34,912 KB |
testcase_18 | AC | 34 ms
34,924 KB |
testcase_19 | AC | 36 ms
34,928 KB |
testcase_20 | AC | 39 ms
35,008 KB |
testcase_21 | AC | 39 ms
34,944 KB |
testcase_22 | AC | 39 ms
34,952 KB |
testcase_23 | AC | 43 ms
35,124 KB |
testcase_24 | AC | 42 ms
35,004 KB |
testcase_25 | AC | 42 ms
35,076 KB |
testcase_26 | AC | 47 ms
35,424 KB |
testcase_27 | AC | 48 ms
35,288 KB |
testcase_28 | AC | 48 ms
35,244 KB |
testcase_29 | AC | 48 ms
35,256 KB |
testcase_30 | AC | 48 ms
35,228 KB |
testcase_31 | AC | 44 ms
35,012 KB |
testcase_32 | AC | 44 ms
35,020 KB |
testcase_33 | AC | 44 ms
35,036 KB |
testcase_34 | AC | 44 ms
35,028 KB |
testcase_35 | AC | 44 ms
35,240 KB |
testcase_36 | AC | 44 ms
34,948 KB |
testcase_37 | AC | 40 ms
35,008 KB |
testcase_38 | AC | 44 ms
35,032 KB |
testcase_39 | AC | 43 ms
35,048 KB |
testcase_40 | AC | 44 ms
34,952 KB |
testcase_41 | AC | 26 ms
35,008 KB |
testcase_42 | AC | 26 ms
34,940 KB |
testcase_43 | AC | 26 ms
35,088 KB |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <numeric> #define rep(x, to) for (int x = 0; x < (to); x++) #define REP(x, a, to) for (int x = (a); x < (to); x++) #define foreach(itr, x) for (typeof((x).begin()) itr = (x).begin(); itr != (x).end(); itr++) using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<long, long> PLL; const ll MOD = (ll)(1e+9 + 7); int N, K; vector<int> G[2005]; vector<ll> dp[2005]; //dp[i][j] iを根とした部分グラフにj個塗る場合は何通りあるか ll dfs(int cur, int prev) { int sum = 1; //curを根とした部分グラフに存在する頂点の数 dp[cur][0] = 1; rep(i, G[cur].size()) { int adj = G[cur][i]; // 隣接ノード if (adj == prev) continue; int num = dfs(adj, cur); vector<ll> tmp(2005, 0); for (int j = 0; j <= sum; j++) { for (int k = 0; k <= num; k++) { tmp[j + k] += (dp[cur][j] * dp[adj][k]) % MOD; tmp[j + k] %= MOD; } } dp[cur] = tmp; sum += num; } dp[cur][sum] = 1; return sum; } int a, b; int main() { rep(i, 2005) dp[i].resize(2005, 0); cin >> N >> K; while (cin >> a >> b) { G[a].push_back(b); G[b].push_back(a); } dfs(0, -1); #if 0 rep(i, 5) rep(j, 5) { printf("%d%c", dp[i][j], j == 5-1 ? '\n' : ' '); } #endif cout << dp[0][K] << endl; return 0; }