zoj2734-Exchange Cards(DFS)

ltstudio

　　给出要交换的卡片价值n，然后给出m个卡片，每个卡片的价值和数目，问你能有多少种来组成一个n
　　dfs往后搜索，dfs(left,index)从index往后搜，left是剩余的价值，if(left==0)种类++;
　　最蛋疼的是输出格式，让我纠结了一小会儿,PE了3次



#include <stdio.h>
#include <string.h>
struct cost{
int v,cnt;
}costs[20];
int val,n,num;
void dfs(int left,int index)
{
if(left==0){num++ ;return ;}
for(int i=index;i<n;i++)
{
if(costs.cnt>0&&left>=costs.v)
{
costs.cnt--;
dfs(left-costs.v,i);
costs.cnt++;
}   
}
}
int main()
{
bool flag=true;
while(scanf("%d%d",&val,&n)!=EOF)
{
num=0;
for(int i=0;i<n;i++)
scanf("%d%d",&costs.v,&costs.cnt);
dfs(val,0);
if(!flag)printf("\n");
if(flag)flag=false;
printf("%d\n",num);
}
}