13D:拖延症

总时间限制:: 1000ms
内存限制:: 65536kB

描述

Tony老师是一个自由职业者。他手中有一份接下来15天的每日工作安排，他要选择一些日子来工作。
每天的工作会带来一定的收入w_i，但会消耗一定的精神值s_i。
Tony老师最初一共有S点精神值；如果进行到某天，他的剩余精神值不足以完成当天的任务，那么他就不会开始这项任务。
另外，Tony老师有严重的拖延症，他在最后5天的工作天数一定要比前10天的加起来多（或者相等）。

请你帮Tony老师计算一下，他这三个礼拜最多可以赚到多少钱？

输入

第一行是一个正整数S，表示Tony老师一开始的精神值。（保证所有精神值加起来不超过int的范围）
随后是15行，每行2个整数，分别表示当天工作的收入wi和要消耗的精神值si。

输出

一个整数，Tony老师最多可以赚到的钱数。

样例输入

样例输出

提示

样例解释：
最后5天每天都工作。
前10天中，第四天（8 2）工作，然后再在6-10天中（5 4）选择4天工作即可。

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 int w[18];
 6 int s[18];
 7 bool work[18];
 8 int ss;
 9 int maxsum = -1;
10 void dfs(int x, int left){ //考虑第x天是否干活，剩下多少精力
11     if(x==16){
12         int first10 = 0, last5 = 0, sum = 0;
13         for(int i = 1; i <= 10; i++)
14             if(work[i]){
15                 first10++;
16                 sum+=w[i];
17             }
18         for(int i = 11; i <= 15; i++){
19             if(work[i]){
20                 last5++;
21                 sum+=w[i];
22             }
23         }
24         if(last5>=first10){
25             maxsum = max(maxsum, sum);
26         }
27         return;
28     }
29     if(left>=s[x]){
30         work[x] = true;
31         dfs(x+1, left-s[x]);
32         work[x] = false;
33         dfs(x+1, left);
34     } 
35     else dfs(x+1, left);
36 }
37 int main(){
38     cin>>ss;
39     int i;
40     for(i = 1; i <= 15; i++)
41         cin>>w[i]>>s[i];
42     dfs(1,ss);
43     cout<<maxsum<<endl;
44     return 0;
45 }