牛客网2018暑期训练 第三场 a题

时间：2023-12-06 17:22:26
#include <bits/stdc++.h>

using namespace std;

vector<int> path;

const int maxn = ;

short dp[maxn][maxn][maxn][maxn][maxn];

bool tp[maxn][maxn][maxn][maxn][maxn];

int P,C,A,M;

int p[maxn],c[maxn],a[maxn],m[maxn],g[maxn];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<= n; ++i)

        scanf("%d%d%d%d%d",p+i,c+i,a+i,m+i,g+i);

    scanf("%d%d%d%d",&P,&C,&A,&M);

    for(int i = ; i<=n; ++i)

    {

        for(int ip = P; ip>=p[i]; --ip)

            for(int ic = C; ic >= c[i]; --ic)

                for(int ia = A; ia >= a[i]; --ia)

                    for(int im = M; im >= m[i]; --im)

                    {

                        dp[i][ip][ic][ia][im] = dp[i-][ip][ic][ia][im];

                        if(dp[i][ip][ic][ia][im] < dp[i-][ip-p[i]][ic-c[i]][ia-a[i]][im-m[i]]+g[i])

                        {

                            dp[i][ip][ic][ia][im] = dp[i-][ip-p[i]][ic-c[i]][ia-a[i]][im-m[i]]+g[i];

                            tp[i][ip][ic][ia][im] = true;

                        }

                    }

    }

    int ans = ;

    //cout << dp[1][1][0][2][1] << endl;

    //cout << dp[n][P][C][A][M] << endl;

    for(int i = n; i>=; --i)

    {

        if(tp[i][P][C][A][M] == true)

        {

            P-=p[i];

            C-=c[i];

            A-=a[i];

            M-=m[i];

            ans ++;

            path.push_back(i-);

        }

    }

    cout << ans << endl;

    for(int i = path.size()-; i>=; --i)

        cout << path[i] << " ";

    cout << path[] << endl;

}

01 背包+路径输出

基本没什么好解释的

相关文章