HDU 2614 Beat 【DFS】

题目

Zty is a man that always full of enthusiasm. He wants to solve every kind of difficulty ACM problem in the world. And he has a habit that he does not like to solve
a problem that is easy than problem he had solved. Now yifenfei give him n difficulty problems, and tell him their relative time to solve it after solving the other one.
You should help zty to find a order of solving problems to solve more difficulty problem.
You may sure zty first solve the problem 0 by costing 0 minute. Zty always choose cost more or equal time’s problem to solve.

输入

The input contains multiple test cases.
Each test case include, first one integer $n(2<n<15)$. express the number of problem.
Than $n$ lines, each line include $n$ integer $T_{ij}(0<=T_{ij}<10)$, the $i$’s row and $j$’s col integer $T_{ij}$ express after solving the problem $i$, will cost $T_{ij}$ minute to solve the problem $j$.

输出

For each test case output the maximum number of problem zty can solved.

样例输入

3
0 0 0
1 0 1
1 0 0
3
0 2 2
1 0 1
1 1 0
5
0 1 2 3 1
0 0 2 3 1
0 0 0 3 1
0 0 0 0 2
0 0 0 0 0

样例输出

3
2
4

提示

sample one, as we know zty always solve problem $0$ by costing $0$ minute.
So after solving problem $0$, he can choose problem $1$ and problem $2$, because $T_{01}\ge 0$ and $T_{02}\ge 0$.
But if zty chooses to solve problem $1$, he can not solve problem $2$, because $T_{12}<T_{01}$.
So zty can choose solve the problem $2$ second, than solve the problem $1$.

题目分析

得到的二维数组中$T_{ij}$表示解决问题$i$后解决问题$j$的耗时。因为题目耗时要不小于上一题，得到解题顺序$i,j,k$的关系式$T_{ij}\le T_{jk}$。以此比较，即采用深度优先搜索策略。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;int n,a[21][21],b[16],max_n,cnt;int MAX(int x,int y)
{
    return x>y?x:y;
}void MaxPro(int x,int y)\\dfs
{
    max_n=MAX(max_n,cnt);if(max_n == n)return ;for(int i = 1;i<n;++i){
    if(b[i] != 1)if(a[y][i]>=a[x][y])\\时间关系式比较{
    b[i]=1;++cnt;MaxPro(y,i);\\解决当前问题i--cnt;b[i]=0;}}
}int main()
{
    while(scanf("%d",&n)!=EOF){
    memset(b,0,sizeof(b));\\刷新for(int i = 0;i<n;++i)for(int j = 0;j<n;++j)scanf("%d",&a[i][j]);cnt=2;max_n=0;b[0]=1;for(int i = 1;i < n;++i)\\依次设置开始题目{
    b[i]= 1;MaxPro(0,i);b[i]= 0;}cout<<max_n<<endl;}return 0;
}

运行结果

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2614