HDU 1681 Frobenius

题目链接：Frobenius

思路：想了很久还是没转过弯来。

递推。

初始化vis[0] = 1，每次有四种方法扩展，这样能扩展到所有能被表示的数。上界的判定，如果一万以内的数都能被表示，那以后的数肯定就都能被表示。

/*
HDU 1681 递推。if (vis[i] == 1) {vis[i+a] = vis[i+b] = vis[i+c] = vis[i+d] = 1; }
可以得到所有0~10^6以内不能被表示的数。然后，判断最大是不是<10^6，只要循环到一百万零一万就可以了。
因为四个数范围都<=一万。
*/


#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define maxn 2000000

bool vis[maxn];

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int a, b, c, d;
        memset(vis, 0, sizeof(vis));
        scanf("%d%d%d%d", &a, &b, &c, &d);
        int ans = -1, cnt = 0;
        vis[0] = 1;

        for (int i=0; i<=maxn/2+a+b+c+d; ++i) {
            if (vis[i]) {
                vis[i+a] = vis[i+b] = vis[i+b] = vis[i+c] = vis[i+d] = 1;
            }
            else {
                if (i <= maxn/2) cnt++;
                ans = max(ans, i);
            }
        }

        if (ans > maxn/2) ans = -1;
        printf("%d
%d
", cnt, ans);
    }
    return 0;
}