题目链接 https://www.luogu.org/problem/P5020 玄学题目。。。。可以用筛表,动规,搜索做 筛表 从小到大枚举,筛掉可以表示出来的数,剩下的数就是必须要选的(也就是答案)。 #includebit
题目链接 https://www.luogu.org/problem/P5020
玄学题目。。。。可以用筛表,动规,搜索做
筛表
从小到大枚举,筛掉可以表示出来的数,剩下的数就是必须要选的(也就是答案)。
#include<bits/stdc++.h> using namespace std; int dp[25005], t, a[105], n, sum; int main() { cin >> t; while(t--) { memset(a, 0, sizeof(a)); memset(dp, 0, sizeof(dp)); sum = 0; cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; dp[a[i]] = 2; } sort(a+1, a+1+n); for(int i = 1; i <= a[n]; i++) { if(dp[i] > 0) { for(int j = 1; j <= n; j++) if(i+a[j] <= a[n]) dp[i+a[j]] = 1; else break; } } for(int i = 1; i <= a[n]; i++) if(dp[i] == 2) sum++; cout << sum << endl; } return 0; }
动态规划
/* 状态 m, dp[i] dp[i]代表面值为i的纸币最多有几种表示 注意这是个刚好装满的完全背包问题(注意初始化) dp[i] = max(dp[i], dp[i-a[i]]+1); */ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int a[105], n, q[30000], t, ans; int main() { cin >> t; while(t--) { ans = 0; memset(q,-63,sizeof q); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; q[0]=0; for(int i = 1; i <= n ; i++) for(int j = a[i]; j <= 25005; j++) q[j] = max(q[j], q[j-a[i]]+1); for(int i = 1; i <= n; i++) if(q[a[i]] == 1) ans++; cout << ans << endl; } return 0; }
启示;刚好装满问题中1.将dp[i] 初始化为-inf ,dp[i] = max(dp[i], dp[i-a[i]]+1);2.没有初始化dp[i],需要再加一层循环,极大的增加复杂度。