滚动数组和压位数组优化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;
}
投递知乎等公司10个岗位 >