AcWing 3382. 整数拆分
乍一眼看到还以为做个解空间树和dfs就做出来了...
#include
using namespace std;
const int MOD=1e9;int n,ans;
void dfs(int x){if(x<0)return;if(x==0)ans++;for(int i=1;i<=x;i=i<<1)dfs(x-i);
}int main(){cin>>n;dfs(n);cout< 运行了一下样例7结果输出了31，...不同位置的1并不能产生贡献，所以拆出来的数要不是降序的。
即每拆一步不能比前一步拆的少，至少要相等。
#include
using namespace std;
const int MOD=1e9;int n,ans;
void dfs(int x,int pre){if(x<0)return;if(x==0)ans++;for(int i=1;i<=x;i=i<<1)if(i>=pre)dfs(x-i,i);
}int main(){cin>>n;dfs(n,0);cout< 样例也过了，但是试了一下极限范围，大概220左右就要1秒了，所以题目范围1e6肯定是过不去的，不过还是想看看能过几个点。
对于这种题目，接下来有三种思路：
确定合适的剪枝策略，实现记忆化搜索。
打出前几个数据，找规律。
改用动态规划（根据目标答案定义状态，找状态转移方程）
管他三七二十一，找个规律先。
看了一眼数据都是2个2个一样的出现，凑了一下发现f[i]=f[i/2]+f[i-2]。
AC代码
#include
using namespace std;long long f[1000001],n;int main(){f[1]=1,f[2]=2;for(int i=3;i<=1000000;++i)f[i]=(f[i/2]+f[i-2])%1000000000;cin>>n;cout< 
但是这种方法并非正道，因为这里已经告诉你要拆的是多少了，如果说每次要拆的数都是输入数据给定的，那找规律肯定找不出来。
再看第一种思路，能否定出剪枝策略。
可以发现解空间树中，4这个数字被反复进行拆数，定下数字4能拆出的所有可能，那么以后拆4只要查表即可。
但是此处记忆化时，这个4能拆出的可能性和先前的pre拆过来是多少，会影响4能拆出的方案数。
所以memo表至少为memo[22][1000001]。（显然爆空间了，所以只能考虑动态规划）
考虑动态规划的时候，由于先前剪枝策略可知最多开一维数组，若定义dp[i][j] 为：前i个2次幂凑成数字j的方案数，会发现依旧要爆空间，所以只定义核心状态，即：#根据目标答案定义状态，找状态转移方程
定义dp[i] 为：用2次幂凑成整数i的方案数
得到：dp[i]+=dp[i-j]，j为2次幂
整数4也要根据整数2推出，所以正序遍历。
内外循环怎么放遵循递推式，如推的时候要保证拆的数是升序，所以所有情况都从1开始递推，所以2次幂要放在外部循环，而不能放在内部循环。
AC代码
#include
using namespace std;long long n,dp[1000001];int main(){cin>>n;dp[0]=1;for(int j=1;j<=n;j=j<<1)for(int i=1;i<=n;++i)if(i-j>=0)dp[i]=(dp[i]+dp[i-j])%1000000000;cout<
上一篇：C语言实例：判断元音/辅音，三个数中的最大数，一元二次方程的根。
下一篇： 描写尴尬的好句