Codeforces 998D(打表找规律)

Codeforces 998D
题意：有$1,5,10,50$四种数字，问用$n$个数字，能构成多少个不同的数字?

打表，发现11项后面的数成等差数列，那么直接前面11项打表，后面用等差数列公式算即可。
附打表程序

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const LL whw[20] = {0, 4, 10, 20, 35, 56, 83, 116, 155, 198, 244, 292};

LL n;

void clean() {
}
int solve() {
    clean();
    if (n <= 11ll) printf("%lld\n", whw[n]); else printf("%lld\n", whw[11ll] + (n - 11ll) * 49ll);
    return 0;
}
int main() {
    scanf("%lld", &n), solve();
    return 0;
}

打表程序：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

int n, h[10], ans, vis[10000005], lstans;
int gg[5] = {0, 1, 5, 10, 50};

void dfs(int a, int rm, int tot) {
    if (rm == 0 && !vis[tot]) {
        ans++, vis[tot] = 1;
        return ;
    }
    if (a >= 5) return ;
    for (int i = 0; i <= rm; i++) dfs(a + 1, rm - i, tot + gg[a] * i);
}

void clean() {
    lstans = ans, ms(vis, 0), ms(h, 0), ans = 0;
}
int solve() {
    clean();
    dfs(1, n, 0);
    printf("n=%d, ans=%d, cha=%d\n", n, ans, ans - lstans);
    //printf("%d, ", ans);
    return 0;
}
int main() {
    for (n = 1; n <= 20; n++) solve();
    return 0;
}