洛谷 P1541 [NOIP2010 提高组] 乌龟棋

LL f[N][N][N][N]；表示四种卡片分别用了多少张,因为数据保证到终点时恰好全用完卡片，不需要再开一维记录目前走到那个位置

#include <bits/stdc++.h>		#define fi first
#define se second
#define endl '\n'using namespace std;
using LL = long long;const int N = 40 + 9; int n,m;
LL f[N][N][N][N];//四种卡片分别用了多少张,因为数据保证一定到终点，不需要再开一维记录目前走到那个位置
int a[360];
int g[5];void solve()
{cin >> n>> m;for (int i = 1;i <= n;i ++) cin >> a[i];for (int i = 1;i <= m;i ++)	{int x; cin >> x;g[x] ++;}f[0][0][0][0] = a[1];for (int i1 = 0;i1 <= g[1];i1 ++)for (int i2 = 0;i2 <= g[2];i2 ++)for (int i3 = 0;i3 <= g[3];i3 ++)for (int i4 = 0;i4 <= g[4];i4 ++){int t = 1 + 1 * i1 + 2 * i2 + 3 * i3 + 4 * i4;LL &now = f[i1][i2][i3][i4];if (i1 >= 1) now = max(now,f[i1 - 1][i2][i3][i4] + a[t]);if (i2 >= 1) now = max(now,f[i1][i2 - 1][i3][i4] + a[t]);if (i3 >= 1) now = max(now,f[i1][i2][i3 - 1][i4] + a[t]);if (i4 >= 1) now = max(now,f[i1][i2][i3][i4 - 1] + a[t]);} cout << f[g[1]][g[2]][g[3]][g[4]] << endl;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _ = 1;// cin >> _;while(_--) solve();return 0;
}