yukicoder No.30 たこやき工場
問題概要
省略
解法
メモ化再帰で解いた。サンプルで与えられている図のように辺を張り、dp[i] := i番目の商品が必要な数 とおき、自分の子で必要なものの数から、i番目に必要な個数を計算する形にした。商品nが必要な個数は1個なので、dp[n - 1] = 1となり、それを基底部としている。ほかの部分はu -> vとなっているとき、uの必要な個数は、(vの必要な個数)と(uからvを作るのに、必要な個数)の積でわかる。これをメモしながら、やっていけばいい。
ミス
図のグラフと逆向きのDAGではじめ書いたけど、TLE。治せなかった。
コード
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cmath> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) const int INF = 1e9; int n, m; vector<pair<int, int> > G[110]; vector<pair<int, int> > rG[110]; int dp[110]; int dfs(int u){ if(u == n - 1){ return dp[u] = 1; } if(dp[u]) return dp[u]; int ret = 0; for(auto v : G[u]){// u -> v.first ret += dfs(v.first) * v.second; } return dp[u] = ret; } int main(void){ cin >> n >> m; rep(i, m){ int p, q, r; cin >> p >> q >> r; p--; r--; //p -> r G[p].push_back(make_pair(r, q)); rG[r].push_back(make_pair(p, q)); } rep(i, 110) dp[i] = 0; rep(i, n){ dfs(i); } rep(i, n - 1){ if(rG[i].size() != 0){ printf("0\n"); }else{ printf("%d\n", dp[i]); } } return 0; }