2018年360春招笔试编程题第二题

#include<iostream>
#include<vector>

using namespace std;

int a[8][3] = { {0, 0, 0}, {0, 1, 2}, {0, 2, 1}, {1, 1, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0} };

int getNum(int r, int g, int b)
{
    vector<vector<vector<vector<int>>>> mat(8, vector<vector<vector<int>>>(r+1, vector<vector<int>>(g+1, vector<int>(b+1, 0))));
    for (int i = 1; i < 8; ++i)
    {
        for (int j = r; j >= 0; j--)
        {
            for (int n = g; n >= 0; n--)
            {
                for (int m = b; m >= 0; m--)
                {
                    int t1 = a[i][0] == 0 ? INT_MAX : j / a[i][0];
                    int t2 = a[i][1] == 0 ? INT_MAX : n / a[i][1];
                    int t3 = a[i][2] == 0 ? INT_MAX : m / a[i][2];
                    int bound = (t1 < t2) ? t1 : t2;
                    bound = (bound < t3) ? bound : t3;
                    int t4 = mat[i - 1][j][n][m];
                    for (int k = 1; k <= bound; ++k)
                    {
                        int t5 = mat[i - 1][j - k*a[i][0]][n - k*a[i][1]][m - k*a[i][2]] + k;
                        t4 = (t4 > t5) ? t4 : t5;
                    }
                    mat[i][j][n][m] = t4;
                }
            }
        }
    }
    return mat[7][r][g][b];
}

int main()
{
    int num;
    int r, g, b;
    cin >> num;
    while (num > 0)
    {
        cin >> r >> g >> b;
        cout << getNum(r, g, b) << endl;
        num--;
    }

    system("pause");
    return 0;
}