题解 P2725 【邮票 Stamps】

小康平方 · 2019-06-30 20:42:32 · 题解

罕见的一篇深搜做法，望通过！

#include <cstdio>
#include <iostream>
using namespace std;

int Answer(int K, int N, int a[]);
void Input(int a[], int N);
bool Solve(int K, int N, int Sum, int a[]);

int main()
{
    int K, N;                   // K 表示邮票数量上限， N 表示邮票面值种数。 
    cin >> K >> N;
    int a[N];
    Input(a, N);                // 输入每张邮票的面值。 
    cout << Answer(K, N, a);    // 输出结果，即最大的邮票可表示的面值。 
    return 0;
}

void Input(int a[], int N)
{
    for(int i=0; i<N; ++i)
        cin >> a[i];
}

int Answer(int K, int N, int a[])       // 逐个测试，直到凑不成停下并返回结果。 
{
    int ret=1;
    while ( Solve(K, N, ret, a) )       // 如果可以，则继续。 
        ++ret; 
    return ret;
}

bool Solve(int K, int N, int Sum, int a[])  // Sum 表示所求得的值。 
{
    // 枚举法 深度优先搜索 （递归）
    if ( Sum < 0 )  return false;           // 如果小于 0 则失败。 
    if ( Sum = 0 )  return true;            // 正好为零，凑成所求值。 
    // 如果大于 0 ，则…… 
    for(int i=0; i<N; ++i)                  // 遍历每一种邮票 
        for(int j=0; j<K; ++j)              // 遍历最高 K 遍 
            if( Solve(K-1, N, Sum-a[i], a) )
                return true;
}