蒟蒻求调,样例都没过的屑代码
查看原帖
蒟蒻求调,样例都没过的屑代码
777318
Normal_Travler楼主2024/4/18 20:04

孩子刚学c++没想到写dp都能错,救救蒟蒻吧

#include <bits/stdc++.h>
using namespace std;

const int N = 355, M = 125, M2 = 45;
int n, m, p[5], a[N], f[M2][M2][M2][M2], maxx = -114514;

int getmax(int a, int b, int c, int d) {//一个比较四个数值的最大值的函数
	int lita, litb;
	lita = a > b ? a : b;
	litb = c > d ? c : d;
	return lita > litb ? lita : litb;
}

int main() {
	scanf("%d%d", &n, &m);//读入数据
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);//读入每个格子的数据
	for (int i = 1, aa; i <= m; i++) {
		scanf("%d", &aa);//读入卡牌数据;加桶数组
		p[aa] += 1;
	}
	f[0][0][0][0] = a[1];//边界设置为起点格子数据
	for (int i = 0; i <= p[1]; i++)
		for (int j = 0; j <= p[2]; j++)
			for (int q = 0; q <= p[3]; q++)
				for (int z = 0; z <= p[4]; z++) {
					f[i][j][q][z] = getmax(	    f[i == 0 ? 0 : i - 1][j][q][z]
					                        ,	f[i][j == 0 ? 0 : j - 1][q][z]
					                        ,	f[i][j][q == 0 ? 0 : q - 1][z]
					                        , 	f[i][j][q][z == 0 ? 0 : z - 1]);
					//dp求上一步最大是多少
					int a_num=i+j*2+q*3+z*4;
					f[i][j][q][z]+=a[a_num];//加上本格数据
					maxx=max(maxx,f[i][j][q][z]);//因为没想出凑和为n的非暴力枚举思路,所以偷懒把答案改为了dp数组里最大的数据

				}


	printf("%d",maxx);//输出dp数组里最大的数据
	
	return 0;
}
2024/4/18 20:04
加载中...