Codeforces 846 B Math Show DFS + 贪心

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

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

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

代码：

#include <iostream>
#include <cstdio>
#include <map>
#include <iterator>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
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;
}

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