滚动数组和压位数组优化dp

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=357;
int const T=42;
int n,m;
int a[N],t[5];
int f[T][T][T];
int main(){
	cin >> n >> m;
	for(int i=1;i<=n;++i) cin >> a[i];
	for(int i=1,x;i<=m;++i) {
		cin >> x;t[x]++;
	}
	int ans=0; 
	for(int i=0;i<=t[1];++i){
		for(int j=0;j<=t[2];++j){
			for(int k=0;k<=t[3];++k){
				for(int l=0;l<=t[4];++l){
					int z=1+i+2*j+3*k+4*l,z2=0;
					if(i-1>=0) z2=max(z2,f[j][k][l]);
					if(j-1>=0) z2=max(z2,f[j-1][k][l]);
					if(k-1>=0) z2=max(z2,f[j][k-1][l]);
					if(l-1>=0) z2=max(z2,f[j][k][l-1]);
					f[j][k][l]=z2+a[z];
				}
			}
		}
	}
	cout << f[t[2]][t[3]][t[4]];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=357;
int const T=42;
int n,m;
int a[N],t[5];
int f[70647]; //41*41*41+41*41+41
int L(int j,int k,int l){
	return j*1681+k*41+l;
}
int main(){
	cin >> n >> m;
	for(int i=1;i<=n;++i) cin >> a[i];
	for(int i=1,x;i<=m;++i) {
		cin >> x;t[x]++;
	}
	int ans=0; 
	for(int i=0;i<=t[1];++i){
		for(int j=0;j<=t[2];++j){
			for(int k=0;k<=t[3];++k){
				for(int l=0;l<=t[4];++l){
					int z=1+i+2*j+3*k+4*l,z2=0;
					if(i-1>=0) z2=max(z2,f[L(j,k,l)]);
					if(j-1>=0) z2=max(z2,f[L(j-1,k,l)]);
					if(k-1>=0) z2=max(z2,f[L(j,k-1,l)]);
					if(l-1>=0) z2=max(z2,f[L(j,k,l-1)]);
					f[L(j,k,l)]=z2+a[z];
				}
			}
		}
	}
	cout << f[L(t[2],t[3],t[4])];
	return 0;
}