BZOJ 1198 [HNOI2006]军机调度：dfs

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1198

题意：

　　有n个雇佣军，m个任务。

　　第i个雇佣军能够参加cnt个任务，分别为temp[0 to cnt-1]。

　　第i个任务开始时间为start[i]，结束时间为over[i]，需要person[i]个人参加才能够完成，完成的报酬为reward[i]。

　　一项只需要n个人来完成的任务，如果执行该任务的人数p大于n,那么反而会得到更少的报酬，即原报酬的1/(p-n+1)。

　　一个人不能同时执行两项任务，也不能中途加入或者退出任务。但可以不执行任何任务。

　　问你能够获得的最大报酬。

题解：

　　dfs暴搜。。。

　　表示状态：

　　　　dfs(mis, per, now, val)

　　　　mis：考虑到第mis个任务

　　　　per：考虑到第per个人

　　　　now：已经参加任务mis的人数

　　　　val：已经获得的报酬（不算mis）

　　dfs：

　　　　首先按任务的start从小到大排序。

　　　　（1）mis == m：

　　　　　　　　搜到底了，更新ans = max val。

　　　　（2）per == n || now == mission[mis].person：

　　　　　　　　per == n 表示没有人可选了

　　　　　　　　now == mission[mis].person 表示人数已经达到任务mis的要求，再加人报酬会变小，不加人可能使答案更优。

　　　　　　　　此时进入到下一个任务 mis + 1，然后return当前的dfs（不存在）。

　　　　（3）fre[per] < mission[mis].start && edge[per][mission[mis].idx]

　　　　　　　　数组fre[per]代表在之前的决策中，士兵per所执行任务的最后一天。

　　　　　　　　fre[per] < mission[mis].start：任务mis开始时，士兵per之前的任务已结束。

　　　　　　　　edge[per][mission[mis].idx]：士兵per可以参加任务mis。

　　　　　　　　若满足，则让士兵per参加mis。更新fre[per]，dfs(mis,per+1,now+1,val)，然后恢复fre。

　　　　（4）dfs(mis,per+1,now,val)：

　　　　　　　　也可以不选per。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #define MAX_N 15

 #define MAX_M 20

 using namespace std;

 struct Mission

 {

     int start;

     int over;

     int person;

     int reward;

     int idx;

     Mission(int _start,int _over,int _person,int _reward,int _idx)

     {

         start=_start;

         over=_over;

         person=_person;

         reward=_reward;

         idx=_idx;

     }

     Mission(){}

     void read_mission(int _idx)

     {

         cin>>start>>over>>person>>reward;

         idx=_idx;

     }

     friend bool operator < (const Mission &a,const Mission &b)

     {

         return a.start<b.start;

     }

 };

 int n,m;

 int ans=;

 int fre[MAX_N];

 bool edge[MAX_N][MAX_M];

 Mission mission[MAX_M];

 void read()

 {

     memset(edge,false,sizeof(edge));

     cin>>n>>m;

     for(int i=;i<n;i++)

     {

         int counter;

         cin>>counter;

         for(int j=;j<counter;j++)

         {

             int temp;

             cin>>temp;

             edge[i][temp-]=true;

         }

     }

     for(int i=;i<m;i++)

     {

         mission[i].read_mission(i);

     }

 }

 void dfs(int mis,int per,int now,int val)

 {

     if(mis==m)

     {

         ans=max(ans,val);

         return;

     }

     if(per==n || now==mission[mis].person)

     {

         int adv=(now==mission[mis].person?mission[mis].reward:);

         dfs(mis+,,,val+adv);

         return;

     }

     if(fre[per]<mission[mis].start && edge[per][mission[mis].idx])

     {

         int temp=fre[per];

         fre[per]=mission[mis].over;

         dfs(mis,per+,now+,val);

         fre[per]=temp;

     }

     dfs(mis,per+,now,val);

 }

 void solve()

 {

     memset(fre,,sizeof(fre));

     sort(mission,mission+m);

     dfs(,,,);

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

BZOJ 1198 [HNOI2006]军机调度：dfs

最新文章

热门文章