主题链接：HDU 2616 Kill the monster

意甲冠军：有N技能比赛HP有M怪物，技能（A，M），能伤害为A。当怪兽HP<=M时伤害为2*A。

求打死怪兽（HP<=0）用的最少技能

方法一：将技能全排列。计算伤害。得到答案。

方法二：搜索，详细看代码。

全排列AC代码：

#include<stdio.h>

#include<algorithm>

using namespace std;

struct node

{

    int p,v;

};

struct node st[30];

int main()

{

    int n,d,i;

    int t[30];

    int ans;

    while(scanf("%d %d",&n,&d)!=EOF)

    {

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

        {

            scanf("%d %d",&st[i].p,&st[i].v);//p掉血，V double

            t[i]=i;

        }

        int sum;

        ans=100;

        do

        {

            sum=d;

            int count=0;

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

            {

                if(sum<=st[t[i]].v)

                    sum-=st[t[i]].p*2;

                else

                    sum-=st[t[i]].p;

                count++;

                if(sum<=0)

                    break;

            }

            if(sum<=0)

                ans=min(ans,count);

        }while(next_permutation(t,t+n));

        if(ans==100)

            printf("-1\n");

        else

            printf("%d\n",ans);

    }

    return 0;

}

搜索AC代码：

#include<stdio.h>

#include<algorithm>

using namespace std;

struct spell

{

	int a,m;

};

struct spell sp[20];

int n,ans,flag;

bool vis[30];

void dfs(int p,int sum)

{

	int i;

	if(sum<=0)

	{

		flag=1;

		ans=min(ans,p);

		return ;

	}

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

	{

		if(!vis[i])

		{

			vis[i]=true;

			if(sum<=sp[i].m)

				dfs(p+1,sum-sp[i].a*2);

			else

				dfs(p+1,sum-sp[i].a);

			vis[i]=false;

		}

	}

}

int main()

{

	int i;

	int m;

	while(scanf("%d %d",&n,&m)!=EOF)

	{

		flag=0;

		memset(vis,false,sizeof vis);

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

			scanf("%d %d",&sp[i].a,&sp[i].m);

		ans=n;

		dfs(0,m);

		if(flag)

			printf("%d\n",ans);

		else

			printf("-1\n");

	}

	return 0;

}