Codeforces 846 B Math Show DFS + 贪心-白红宇

Codeforces 846 B Math Show DFS + 贪心

阅读量：6502 次

发布时间：2019-06-24

本文共 1203 字，大约阅读时间需要 4 分钟。

　　题目链接： http://codeforces.com/contest/846/problem/B

　　题目描述：有N个节点，每个节点有相同的K个子节点，每个子节点有时间花费，完成一个子节点获得1分，每完成一个节点的所有子节点获得额外一分，问你在M s内最多可以获得多少分

　　解题思路：我们贪心的来思考这个问题，最优解一定是由 所有的最小值的集合 或者 k个子节点的集合 组合而成的，而且每一个最优解一定是由两个之一最优的那么这样的话我们就回溯的时候取得最优值， dfs一遍就好了

　　代码：

#include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;typedef long long ll;const int maxn = 50;int a[maxn];int n, k, m;int dfs( int d, int sum ) { if( d > n ) return 0; int ans = 0; if( sum >= a[0] ) ans = max( ans, k+1+dfs(d+1, sum-a[0]) ); int score = 0; for( int i = 1; i <= k; i++ ) { if( sum >= (n-d+1) * a[i] ) { score += (n-d+1); if( i == k ) score += (n-d+1); sum -= (n-d+1) * a[i]; } else { score += sum / a[i]; if( i == k ) score += sum / a[i]; sum -= (sum/a[i])*a[i]; break; } } return max(ans, score);}int main() { cin >> n >> k >> m; a[0] = 0; for( int i = 1; i <= k; i++ ) { cin >> a[i]; a[0] += a[i]; } sort(a+1,a+k+1); cout << dfs(1,m) << endl; return 0;}

View Code

　　思考：自己这道题没有做出来，是真的菜......所以说还得多练啊......

转载于:https://www.cnblogs.com/FriskyPuppy/p/7616460.html

你可能感兴趣的文章