【牛客算法周周练8】

A-小A买彩票

AC代码

#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e5 + 5e4 + 7;
ll dp[37][127];//dp[买奖次数][得到的奖金数量] = 方案数
//全局变量区

ll gcd(ll a, ll b) { return b ? gcd(b, a % b): a; }
//函数预定义区

int main() {
    IOS;
    int n; cin >> n;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= 4 * i; j++)
            for (int k = 1; k <= 4; k++)
                if (j >= k) dp[i][j] += dp[i - 1][j - k];

    ll down = 1ll << 2 * n;//总数：4^n
    ll up = 0;
    for (int i = 3 * n; i <= 4 * n; i++) 
        up += dp[n][i];
    ll factor = gcd(up, down);
    cout << up / factor << "/" << down / factor << endl;
    return 0;
}
//函数区

B-「金」点石成金

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 17;
struct Node {
    int a, b, c, d;
} info[MAX];
int n; 
//全局变量区

ll dfs(int pos, ll money, ll magic);
//函数预定义区

int main() {
    IOS;
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> info[i].a >> info[i].b >> info[i].c >> info[i].d;
    ll ans = dfs(1, 0, 0);
    cout << ans << endl;
    return 0;
}
ll dfs(int pos, ll money, ll magic) {
    if (pos > n) return money * magic;
    int t1 = money + info[pos].a;
    int t2 = magic - info[pos].b;
    if (t2 < 0) t2 = 0;
    ll res1 = dfs(pos + 1, t1, t2);
    t1 = money - info[pos].d;
    t2 = magic + info[pos].c;
    if (t1 < 0) t1 = 0;
    ll res2 = dfs(pos + 1, t1, t2);
    return max(res1, res2);
}
//函数区