并不难想，但也是要练一练写代码的能力
注意一点，这里用o【i】数组记录一个状态是否出现！因为N进制状态压缩，会出现太多太多无用的状态！，显然的会超时
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int n,m,v[7],f[5000050]; bool o[5000050]; int S,ans; bool pan(int *a) { for (int i=1;i<=m;i++) if (a[i]>v[i]) return false; return true; } int main() { scanf("%d%d",&n,&m); int mx=0; for (int i=1;i<=m;i++) scanf("%d",&v[i]),mx=max(mx,v[i]); mx++; S=1; for (int i=1;i<=m;i++) S=S*mx; S--; o[0]=true; for (int i=1;i<=n;i++) { int up,a[7]; scanf("%d",&up); for (int i=1;i<=m;i++) scanf("%d",&a[i]); for (int s=S;s>=0;s--) if (o[s]) //该优化，还是要优化一下这么显然的东西的，因为多余的状态实在太多了 { int k=s,b[7]; for (int j=1;j<=m;j++) { b[j]=k%mx; k=k/mx; } for (int j=1;j<=m;j++) b[j]+=a[j]; if (pan(b)) { int k=0; for (int l=m;l>=1;l--) k=k*mx+b[l]; o[k]=true; f[k]=max(f[k],f[s]+up); ans=max(ans,f[k]); } } /***********************************************/ } printf("%d",ans); return 0; }
