题目讲述了一个等价交换卡片的故事,其实是为了统计一个价值为n的卡片有多少种组合方式。
题目链接:题目
题目思路:
根据现有卡片对能够构成价值n的卡片,进行DFS,找出所有能构成的方式,统计。
代码如下:
#include <iostream>
#include <cstdlib>
using namespace std;
struct card
{
int val;
int num;
}a[11];
int m;
int (const void*p1, const void*p2)
{
return (*(card*)p1).val>(*(card*)p2).val?-1:1;
}
void DFS(int sum,int start ,int &cnt)
{
if(sum==0)
{
cnt++;
}
else
{
for(int i=start;i<m;i++)
{
if(a[i].val<=sum && a[i].num )
{
sum-=a[i].val;
a[i].num--;
DFS(sum,i,cnt);
a[i].num++;
sum+=a[i].val;
}
}
}
}
int main()
{
int n;
int cnt;
int u=0;
int sum;
while(cin>>n>>m)
{
if(u)
cout<<endl;
else
u++;
for(int i=0;i<m;i++)
{
cin>>a[i].val>>a[i].num;
}
qsort(a,m,sizeof(a[0]),comp);
cnt=0;
sum=n;
for(int i=0;i<m;i++)
{
if(a[i].val<=n)
{
sum-=a[i].val;
a[i].num--;
DFS(sum,i,cnt);
a[i].num++;
sum+=a[i].val;
}
}
cout<<cnt<<endl;
}
return 0;
}
近期评论