程序员人生 网站导航

Codeforces Round #286 (Div. 1) C、D

栏目:php教程时间:2015-02-04 09:25:49

C:题目中步数看似很多,其实最多就增长250步左右,由于移动的步数为1 + 2 + 3 + .. n,所以大概只会有sqrt(n)步,所以dp[i][j]表示在i位置,增长为j步的值,然后转移便可

D:这题其实对1个联通块,最多只需要n条边,最少要n - 1条,那末判断的条件,就是这个联通块是不是有环,利用拓扑排序去判便可

代码:

C:

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 30005; int n, d, cnt[N], dp[N][500]; int dfs(int u, int cha) { if (u > 30000) return 0; if (dp[u][cha] != ⑴) return dp[u][cha]; int tmp = d + cha - 250; dp[u][cha] = cnt[u]; int ans = 0; if (tmp > 1) ans = max(ans, dfs(u + tmp - 1, cha - 1)); ans = max(ans, dfs(u + tmp, cha)); ans = max(ans, dfs(u + tmp + 1, cha + 1)); dp[u][cha] += ans; return dp[u][cha]; } int main() { scanf("%d%d", &n, &d); int tmp; for (int i = 0; i < n; i++) { scanf("%d", &tmp); cnt[tmp]++; } memset(dp, ⑴, sizeof(dp)); printf("%d ", dfs(d, 250)); return 0; }

D:

#include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; const int N = 100005; int n, m, du[N], vis[N], have[N], hn; vector<int> g[N], g2[N]; void dfs(int u) { have[hn++] = u; vis[u] = 1; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (vis[v]) continue; dfs(v); } } bool find() { queue<int> Q; for (int i = 0; i < hn; i++) if (!du[have[i]]) Q.push(have[i]); while (!Q.empty()) { int u = Q.front(); Q.pop(); int sz = g2[u].size(); for (int i = 0; i < sz; i++) { int v = g2[u][i]; du[v]--; if (!du[v]) Q.push(v); } } for (int i = 0; i < hn; i++) if (du[have[i]]) return true; return false; } int main() { scanf("%d%d", &n, &m); int u, v; while (m--) { scanf("%d%d", &u, &v); du[v]++; g[u].push_back(v); g[v].push_back(u); g2[u].push_back(v); } int ans = n; for (int i = 1; i <= n; i++) { if (!vis[i]) { hn = 0; dfs(i); if (!find()) ans--; } } printf("%d ", ans); return 0; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐