2 条题解

  • 0
    @ 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;
    }
    
    • 0
      @ 2023-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;
      }
      
      • @ 2023-10-1 17:05:21

        厉害

      • @ 2023-10-1 17:06:42
        #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;
        }
        
    • 1

    信息

    ID
    234
    时间
    1000ms
    内存
    128MiB
    难度
    9
    标签
    递交数
    9
    已通过
    7
    上传者