就是问你,n这个数可以被多少种方案组成。
比如:
算是,方案+完全背包的模板题了。
#include<iostream> #include<cstring> using namespace std; int dp[150]; int main() { int n; while (~scanf("%d", &n)){ memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 1; i <= n;++i) for (int j = i; j <=n; ++j) dp[j] += dp[j - i]; printf("%d\n", dp[n]); } }
我试了试暴力搜索,不幸超时,搜在50以内还可以
#include<iostream> #include<cstring> using namespace std; int num[150],sum, ans; void dfs(int cur, int n) { if (sum == n)ans++; else { for (int i = 1; i <= n; ++i) { if (i >= num[cur - 1]) { sum += i; if (sum <= n) { num[cur] = i; dfs(cur + 1, n); sum -= i; } else{ sum -= i; return; } } } } } int main() { int n; while (~scanf("%d", &n)) { sum = 0, ans=0; memset(num, 0, sizeof(num)); dfs(1, n); printf("%d\n", ans); } }
标签:150,Ignatius,背包,int,sum,include,III,Princess,dp From: https://www.cnblogs.com/ALINGMAOMAO/p/17117681.html