记忆化搜索,但是不对
查看原帖
记忆化搜索,但是不对
798683
1252749383x楼主2023/1/19 23:16
#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<set>
#include<vector>
#include<deque>
#include<cmath>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
const int N = 355;
int a[N];
int b[N];
int cnt[5];
int n;
int m;
int f[41][41][41][41];
int dp(int def, int a1, int a2, int a3, int a4, int sum)
{
	if (def == n)return sum;
	int& res = f[a1][a2][a3][a4];
	if (res)return res;
	if (a1)res = max(res, dp(def + 1, a1 - 1, a2, a3, a4, sum + a[def + 1]));
	if (a2)res = max(res, dp(def + 2, a1, a2 - 1, a3, a4, sum + a[def + 2]));
	if (a3)res = max(res, dp(def + 3, a1, a2, a3 - 1, a4, sum + a[def + 3]));
	if (a4)res = max(res, dp(def + 4, a1, a2, a3, a4 - 1, sum + a[def + 4]));
	return res;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> a[i];
	while (m--) {
		int x;
		cin >> x;
		cnt[x]++;
	}
	cout << dp(1, cnt[1], cnt[2], cnt[3], cnt[4], a[1]);
}
2023/1/19 23:16
加载中...