P2842题解

dongrunxuan · 2023-12-03 20:19:20 · 题解

蒟蒻第一次写题解

思路

一眼dp

但dp题肯定不能用dp做

又知周所众，所有dp题都能被搜索通过

而朴素dfs为指数级别，剪枝后只能拿30—40分，无法通过

怎么将时间呢？

所以我们可以想到……

记忆化搜索！！！

可以在dfs中，传入需要的w值，f数组进行记忆，大大节省时间

代码：

#include <iostream>
#include<queue>
#include <set>
#include<string.h>
using namespace std;
int coin[1000000];
int fff[1000000];
const int inf = 0x7f7f7f7f;
int n, sum;
int dfs(int k)
{
    if (k <= 0)
        return 0; 
    if (fff[k] != 0)
        return fff[k];
    int ans = inf;
    for (int i = 1; i <= n; i++)
    {
        if ( k >= coin[i])
        ans = min(ans, dfs(k - coin[i])+1);
    }
    fff[k] = ans;
    return fff[k];
}
int main()
{ 
    cin >> n>>sum;
    for (int i = 1; i <= n; i++)
    {
        cin >> coin[i];
    }

    cout<< dfs(sum);
    return 0;
}