【Luogu】动态规划六

P1586 四方定理 - 洛谷

思路：

这题其实就是完全背包问题，但是有限制，最多数量只能是 4

所以我们可以定义 dp[i][j] 为 i 用 j 个数拼凑的总方案数

那么转移方程也很明显了，dp[i][j] += dp[i - k*k][j - 1]

具体的，我们用三层循环，一层用于枚举物品（数字），一层用于枚举价值 i，一层用于枚举个数 j

注意初始化 dp[0][0] = 1

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
const int MaxN = 32768;
int f[MaxN + 1][5];void Init()
{f[0][0] = 1;for (int i = 1; i <= sqrt(MaxN); i++){for (int j = i*i; j <= MaxN; j++){for (int k = 1; k <= 4; k++){f[j][k] += f[j - i*i][k - 1];}}}
}void solve()
{int n;cin >> n;cout << f[n][1] + f[n][2] + f[n][3] + f[n][4] << endl;
}
signed main()
{Init();cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

---

P1504 积木城堡 - 洛谷

思路：

很无聊的一题，n个01背包

题目意思就是让我们找到一个最大的每个 01 背包都能拼出的 i

输入很石，要自己判断结束

那我们对于每个背包都做一遍枚举，经典的 能否拼凑xx 问题，用bool即可，然后枚举完后我们检测其中所有的 i，如果是 1，那么存入 tot[i]，其中 tot[i] 代表 i 能拼凑出来的总次数

最后枚举 i，如过存在 tot[i] == n ，说明每个背包都能拼出 i，直接输出即可 

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define int long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int n;cin >> n;vector<int> tot(10005, 0);for (int i = 0; i < n; i++){vector<int> now,dp(10005,0);int x,len = 0;while(1){cin >> x;if (x == -1){break;}now.push_back(x);len += x;}dp[0] = 1;for (int j = 0; j < now.size(); j++){for (int k = len; k >= now[j]; k--){dp[k] |= dp[k - now[j]];}}for (int j = len; j >= 0; j--){tot[j] += dp[j];}}for (int i = 10000; i >= 0; i--){if (tot[i] == n){cout << i;return;}}
}
signed main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}