zoj 2734 Exchange Cards【dfs+剪枝】
Exchange Cards
Time Limit: 2 Seconds Memory Limit: 65536 KB
As a basketball fan, Mike is also fond of collecting basketball player cards. But as a student, he can not always get the money to buy new cards, so sometimes he will exchange with his friends for cards he likes. Of course, different cards have different value, and Mike must use cards he owns to get the new one. For example, to get a card of value 10$, he can use two 5$ cards or three 3$ cards plus one 1$ card, depending on the kinds of cards he have and the number of each kind of card. And Sometimes he will involve unfortunately in a bad condition that he has not got the exact value of the card he is looking for (fans always exchange cards for equivalent value).
Here comes the problem, given the card value he plans to get and the cards he has, Mike wants to fix how many ways he can get it. So it's you task to write a program to figure it out.
Input
The problem consists of multiple test cases, terminated by EOF. There's a blank line between two inputs.
The first line of each test case gives n, the value of the card Mike plans to get and m, the number of different kinds of cards Mike has. n will be an integer number between 1 and 1000. m will be an integer number between 1 and 10.
The next m lines give the information of different kinds of cards Mike have. Each line contains two integers, val and num, representing the value of this kind of card, and the number of this kind of card Mike have.
Note: different kinds of cards will have different value, each val and num will be an integer greater than zero.
Output
For each test case, output in one line the number of different ways Mike could exchange for the card he wants. You can be sure that the output will fall into an integer value.
Output a blank line between two test cases.
Sample Input
5 2
2 1
3 1 10 5
10 2
7 2
5 3
2 2
1 5
Sample Output
1 7
注意输出格式
#include<stdio.h>
#include<string.h>
int n,m,sum,k;
int val[10000010];
void dfs(int cur,int tot)
{
int i,j;
if(tot==n)
{
sum++;
return ;
}
for(i=cur;i<k;i++)
{
if(tot+val[i]<=n)//剪枝
dfs(i+1,tot+val[i]);
while(val[i]==val[i+1]&&i<k-1)//去重
++i;
}
}
int main()
{
int i,t=0;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(t>0) printf("\n");
k=0;
int x,y;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
while(y--)
val[k++]=x;
}
sum=0;
dfs(0,0);
printf("%d\n",sum);
t++;
}
return 0;
}
最新文章
- Sql server函数的学习1(系统变量、错误函数、转换函数)
- JSP内置对象有哪些呢?
- Color Space: HSI
- RabbitMQ学习总结 第六篇:Topic类型的exchange
- 为移动Web应用创建快速响应按钮
- BZOJ 1043 HAOI2008 下落的圆盘 计算几何
- PHP CURL参数详解
- compass安装使用960 Grid System
- oracle 11g dblink配置
- hdu 6059---Kanade&#39;s trio(字典树)
- 【机器学习】正则化的线性回归 —— 岭回归与Lasso回归
- 图解HTTPS建立过程
- TypeScript 实现任务队列
- Pycharm桌面图标(Fedora)
- LaTeX:图形的填充(生成阴影图形)
- Photoshop去图片水印——适用复杂图片上有水印
- SpringMVC点滴(1)
- 菜鸟学SSH(十三)——Spring容器IOC解析及简单实现
- 05: MySQLdb 原生SQL语句操作数据库
- mongodb基础应用