动态规划 与 无敌爆搜(阴的没边)

动态规划

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5+10;
ll dp[N];//代表当前n为i时操作到<=c所需要的最少操作数
const ll p = 1000000007;
int main()
{
    ll n,a,b,c;cin>>n>>a>>b>>c;
    for(int i = 0;i<=c;i++)
        dp[i] = 1;//刚开始先默认0-c的操作次数为1 这里可以从第一个测试样例中看出来。
    for(int i = c+1;i<=n;i++)//遍历剩余情况
    {
       //核心就是 dp[i] = (dp[i]+dp[i-a])%p，dp[i] = (dp[i]+dp[i-b])%p；
       //写成双分支的原因是因为i-a和i-b等于负数时，负数不能作为下标(等于负数其实就是搞定了)也就跟dp[0~c]时一样等于1
       //所以else里面的dp[i-a]和dp[i-b]替换成了1
        if(i-a>0)
            dp[i] = (dp[i]+dp[i-a])%p;
        else
            dp[i] = (dp[i]+1)%p;
        if(i-b>0)
            dp[i] = (dp[i]+dp[i-b])%p;
        else
            dp[i] = (dp[i]+1)%p;
    }
    cout<<dp[n];
    return 0;
}

无敌爆搜(只是想着试试能骗多少分，结果样例3超时，但是提交全对，只能说测试样例比较水)

#include<bits/stdc++.h>
#include <pthread.h>
using namespace std;
using ll = long long;
const ll N = 2e5+10;
ll dp[N];
ll ans;
ll n,a,b,c;
const ll p = 1000000007;
void dfs(ll n)
{
    if(n<=c)
    {
        ans = (ans+1)%p;
        return;
    }
    dfs(n-a);
    dfs(n-b);
}
int main()
{
    cin>>n>>a>>b>>c;
    dfs(n);
    cout<<ans<<endl;
    return 0;
}