0x00 竞赛
0x01 \(dp\)
题目大致就是说，我们有四个篮子(\(A,B,C,D\))，每次给我们四个数(\(a,b,c,d\))，我们可以选择一个数放到对应的篮子里。
篮子的大小是有限制的。
让我们求，四个篮子的最大期望之和。
其实题目的数据范围就已经给足了暗示了 \(O(100)\) 级别。
这个数据范围是在太小了，所以说，如果你的算法时间复杂度太小，那么基本上肯定是错的。
时间复杂度 \(O(\frac{N^{5}}{64})\) 大约在 \(O(10^8)\)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n;
int f[N][N][N][N];
/* f[a][b][c][d] 表示
第 1 个篮子放了 a 个数
第 2 个篮子放了 b 个数
第 3 个篮子放了 c 个数
第 4 个篮子放了 d 个数
的最大期望和 */
/* 状态转移方程
每次给定我们四个数，我们都有 4 中不同的放置方案
1. 选择第 1 个数
f[a][b][c][d] = max(f[a][b][c][d], f[a - 1][b][c][d] + A);
2. 选择第 2 个数
f[a][b][c][d] = max(f[a][b][c][d], f[a][b - 1][c][d] + B);
...
...
*/
int main()
{
cin >> n;
int k = n >> 2;
for(int i = 1; i <= n; i ++ )
{
int A, B, C, D;
cin >> A >> B >> C >> D;
// a, b, c, d 要从 0 开始
for(int a = 0; a <= k; a ++ )
{
for(int b = 0; b <= k; b ++ )
{
for(int c = 0; c <= k; c ++ )
{
for(int d = 0; d <= k; d ++ )
{
// 还要特殊判断一下
// 四个篮子中数的个数不能超过当前出现的数的个数
if(a + b + c + d != i) continue;
if(a) f[a][b][c][d] = max(f[a][b][c][d], f[a - 1][b][c][d] + A);
if(b) f[a][b][c][d] = max(f[a][b][c][d], f[a][b - 1][c][d] + B);
if(c) f[a][b][c][d] = max(f[a][b][c][d], f[a][b][c - 1][d] + C);
if(d) f[a][b][c][d] = max(f[a][b][c][d], f[a][b][c][d - 1] + D);
}
}
}
}
}
cout << f[k][k][k][k] << endl;
return 0;
}