2 条题解
-
0昌孝阳 (changxiaoyang) LV 10 @ 2023-10-1 17:07:16
#include<bits/stdc++.h> #include<unordered_map> using namespace std; typedef long long LL; #pragma warning(disable :4996) typedef unsigned long long ULL; typedef pair<int, int> PII; #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) const int maxn = 1010; const int maxlogn = 20; const int maxc = 1000010; const long double eps = 1e-8; const LL MOD = 998244353; int N, M; vector<int>G[maxn]; int dp[maxn][maxn]; int root = 0; string S; stringstream SS; unordered_map<string, int>um; int score[maxn], sz[maxn]; bool fa[maxn]; void add_edge(int from, int to) { G[from].push_back(to); } void dfs1(int v) { sz[v] = 1; if (!G[v].size()) return; for (int i = 0; i < G[v].size(); i++) { int u = G[v][i]; dfs1(u); sz[v] += sz[u]; } } void dfs2(int v) { dp[v][0] = 0; for (int i = 1; i <= M; i++) dp[v][i] = inf; for (int i = 0; i < G[v].size(); i++) { int u = G[v][i]; dfs2(u); for (int j = sz[v]; j >= 0; j--) { for (int k = 0; k <= min(sz[u], j); k++) dp[v][j] = min(dp[v][j], dp[v][j - k] + dp[u][k]); } } if (v) { for (int i = 0; i <= sz[v]; i++) dp[v][i] = min(dp[v][i], score[v]); } } void solve() { int ans = inf; dfs1(root); dfs2(root); cout << dp[0][M] << endl; } int main() { IOS; char ch; int idx = 0; while (getline(cin, S) && S[0] != '#') { um.clear(); memset(dp, 0x3f, sizeof(dp)); memset(fa, 0, sizeof(fa)); SS.clear(), SS.str(S); SS >> N >> M; for (int i = 0; i <= N; i++) G[i].clear(); for (int i = 0; i < N; i++) { getline(cin, S); SS.clear(), SS.str(S); string country; int value; SS >> country >> value; if (um[country] == 0) um[country] = ++idx; score[um[country]] = value; string sub; while (SS >> sub) { if (um[sub] == 0) um[sub] = ++idx; add_edge(um[country], um[sub]); fa[um[sub]] = true; } } for (auto a : um) { if (!fa[a.second]) add_edge(root, a.second); } solve(); } return 0; }
-
02023-6-10 9:58:49@
#include<bits/stdc++.h> #include<unordered_map> using namespace std; typedef long long LL; //#define int LL #pragma warning(disable :4996) typedef unsigned long long ULL; typedef pair<int, int> PII; #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) const int maxn = 1010; const int maxlogn = 20; const int maxc = 1000010; const long double eps = 1e-8; const LL MOD = 998244353; int N, M; vector<int>G[maxn]; int dp[maxn][maxn]; int root = 0; string S; stringstream SS; unordered_map<string, int>um; int score[maxn], sz[maxn]; bool fa[maxn]; void add_edge(int from, int to) { G[from].push_back(to); } void dfs1(int v) { sz[v] = 1; if (!G[v].size()) return; for (int i = 0; i < G[v].size(); i++) { int u = G[v][i]; dfs1(u); sz[v] += sz[u]; } } void dfs2(int v) { dp[v][0] = 0; for (int i = 1; i <= M; i++) dp[v][i] = inf; for (int i = 0; i < G[v].size(); i++) { int u = G[v][i]; dfs2(u); for (int j = sz[v]; j >= 0; j--) { for (int k = 0; k <= min(sz[u], j); k++) dp[v][j] = min(dp[v][j], dp[v][j - k] + dp[u][k]); } } if (v) { for (int i = 0; i <= sz[v]; i++) dp[v][i] = min(dp[v][i], score[v]); } } void solve() { int ans = inf; dfs1(root); dfs2(root); cout << dp[0][M] << endl; } int main() { IOS; char ch; int idx = 0; while (getline(cin, S) && S[0] != '#') { um.clear(); memset(dp, 0x3f, sizeof(dp)); memset(fa, 0, sizeof(fa)); SS.clear(), SS.str(S); SS >> N >> M; for (int i = 0; i <= N; i++) G[i].clear(); for (int i = 0; i < N; i++) { getline(cin, S); SS.clear(), SS.str(S); string country; int value; SS >> country >> value; if (um[country] == 0) um[country] = ++idx; score[um[country]] = value; string sub; while (SS >> sub) { if (um[sub] == 0) um[sub] = ++idx; add_edge(um[country], um[sub]); fa[um[sub]] = true; } } for (auto a : um) { if (!fa[a.second]) add_edge(root, a.second); } solve(); } return 0; }
- 1
信息
- ID
- 234
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 9
- 已通过
- 7
- 上传者