题解 | #PACM Team#

A是一个改变的背包，就是把条件数目增加了，实际上还是01背包

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N=40;
int f[N][N][N][N];
int p[N], m[N], g[N], a[N], c[N];
bool ans[N][N][N][N][N];
int P, A, C, M;
signed main()
{
	int n;
	sc(n);
	for(int i=1;i<=n;++i)
	{
		cin>>p[i]>>a[i]>>c[i]>>m[i]>>g[i];
	}
	sc(P); sc(A);sc(C);sc(M);
//	cout<<P<<A<<C<<M<<endl;
	for(int i=1; i<=n; ++i)
	{
//		cout<<1;
		for(int pp=P; pp>=p[i]; --pp)
		{
//			cout<<1;
			for(int aa=A; aa>=a[i]; --aa)
			{
//				cout<<1;
				for(int cc=C; cc>=c[i]; --cc)
				{
					for(int mm=M; mm>=m[i]; --mm)
					{
						if(f[pp][aa][cc][mm]<f[pp-p[i]][aa-a[i]][cc-c[i]][mm-m[i]] + g[i])
						{
							f[pp][aa][cc][mm] = f[pp-p[i]][aa-a[i]][cc-c[i]][mm-m[i]] + g[i];
							ans[i][pp][aa][cc][mm]=1;
						}
						
					}
				}
			}
		}
	}
	vector<int> line;
	for(int i=n;i>=1;i--)
	{
		if(a[i] > A || p[i] > P || c[i] > C || m[i] > M)    continue ;
		if(ans[i][P][A][C][M]==1)
		{
			line.push_back(i-1);
			P-=p[i];
			A-=a[i];
			C-=c[i];
			M-=m[i];
		}
	}
	cout<<line.size()<<endl;
	for (auto lin : line) 
	{
		cout << lin<<' ';
    }
	return 0;
}