dp 记忆化搜索

3个1元和1个10元的情况不能少

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <map>

#include <set>

#include <stack>

#include <vector>

#include <sstream>

#include <string>

#include <cstring>

#include <algorithm>

#include <iostream>

#define maxn 20010

#define INF 0x7fffffff

#define inf 10000000

#define ull unsigned long long

#define ll long long

using namespace std;

int a[710][110][100];

int dp(int num, int n1, int n2, int n3)

{

    int &ans = a[n1][n2][n3];

    if(ans >= 0) return ans;

    if(num == 0) return ans = 0;

    else

    {

        ans = INF;

        if(n1 >= 3 && n3 >= 1) ans = min(ans, dp(num-1, n1-3, n2+1, n3-1) + 4);

        if(n1 >= 8) ans = min(ans, dp(num-1, n1-8, n2, n3) + 8);

        if(n1 >= 3 && n2 >= 1) ans = min(ans, dp(num-1, n1-3, n2-1, n3) + 4);

        if(n2 >= 2) ans = min(ans, dp(num-1, n1+2, n2-2, n3) + 2);

        if(n3 >= 1) ans = min(ans, dp(num-1, n1+2, n2, n3-1) + 1);

        return ans;

    }

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t--)

    {

        memset(a, -1, sizeof(a));

        int n1, n2, n3, n4;

        scanf("%d%d%d%d", &n1, &n2, &n3, &n4);

        printf("%d\n", dp(n1, n2, n3, n4));

    }

    return 0;

}