BZOJ2660: [Beijing wc2012]最多的方案
BZOJ2660: [Beijing wc2012]最多的方案
记忆化暴搜+剪枝
一个优秀的剪枝：
当对于当前值处理第i位斐波那契数时，如果它大于第i+1位斐波那契数，对于第i位斐波那契数不取的情况就不再继续搜索下去。
因为对于当前值无法用第1位到第i-1位斐波那契数求和得到。（f[1] + f[2] + ··· + f[i-1] < 当前值）
/************************************************************** Problem: 2660 User: solvit Language: C++ Result: Accepted Time:0 ms Memory:1296 kb ****************************************************************/ #include<bits/stdc++.h> using namespace std; const int maxn = 105; map<long long,long long> dp[maxn]; long long n,f[maxn]; long long dfs(long long x,int id) { if(x == 0)return 1; if(id == 1) { if(x == 1)return 1; else return 0; } if(dp[id][x]) return dp[id][x]; long long ret = 0; if(x >= f[id]) ret += dfs(x-f[id],id-1); if(x < f[id+1]) ret += dfs(x,id-1); dp[id][x] = ret; return ret; } int main() { int i; f[1] = 1; f[2] = 2; scanf("%lld",&n); for(i=3; f[i-1]+f[i-2] <= n; i++){ f[i] = f[i-1] + f[i-2]; } f[i] = f[i-1] + f[i-2]; cout<<dfs(n,i-1)<<endl; }