hdu 2616 Kill the monter
893 ワード
タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=2616
簡単なDFS+トレースです。使用済みのお札を表示します。
元々minはグローバル変数を定義できないことが分かりました。
以下はACコードです
簡単なDFS+トレースです。使用済みのお札を表示します。
#include<iostream>
#include<cstring>
using namespace std;
int a[15],b[15];
int used[15];
int minf;
int n,m;
void DFS(int blood,int cnt)
{
if(cnt>n)
return ;
if(cnt<minf&&blood<=0)
{
minf=cnt;
return ;
}
for(int i=1;i<=n;i++)
{
if(!used[i])
{
used[i]=1;
if(blood<=b[i])
DFS(blood-2*a[i],cnt+1);
if(blood>b[i])
DFS(blood-a[i],cnt+1);
used[i]=0;
}
}
}
int main()
{
while(cin>>n>>m)
{
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
memset(used,0,sizeof(used));
minf=20;
DFS(m,0);
if(minf!=20)
printf("%d
",minf);
else
printf("-1
");
}
return 0;
}
元々minはグローバル変数を定義できないことが分かりました。
以下はACコードです