头像

4_3




离线:2天前


最近来访(105)
用户头像
anss
用户头像
我木jj我怕谁
用户头像
lty2019
用户头像
浮生若梦ღ
用户头像
runningboy001
用户头像
我要AK
用户头像
李向前XingY
用户头像
DraymoNd_
用户头像
饿魔
用户头像
嘟嘟的神秘男友
用户头像
轻丶浮生
用户头像
单车骑士
用户头像
码NB
用户头像
nickelth
用户头像
rushhhhh
用户头像
usx123
用户头像
carryking
用户头像
JasonQ1an
用户头像
海星派大双
用户头像
Lucius7

活动打卡代码 AcWing 479. 加分二叉树

4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;

int n;
int w[N];
int f[N][N], g[N][N];

void dfs(int l, int r)
{
    if (l > r) return;
    int k = g[l][r];
    cout << k << ' ';
    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> w[i];

    for (int len = 1; len <= n; len ++)
        for (int l = 1; l + len - 1 <= n; l ++)
        {
            int r = l + len - 1;
            if (len == 1) f[l][r] = w[l], g[l][r] = l;
            else
            {
                for (int k = l; k <= r; k ++)
                {
                    int left = k == l ? 1 : f[l][k - 1];
                    int right = k == r ? 1 : f[k + 1][r];
                    int score = left * right + w[k];
                    if (f[l][r] < score)
                    {
                        f[l][r] = score;
                        g[l][r] = k;
                    }
                }
            }
        }

    cout << f[1][n] << '\n';

    dfs(1, n);

    return 0;
}


活动打卡代码 AcWing 3745. 牛的学术圈 I

4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int a[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    sort(a + 1, a + n + 1, greater<int>());

    int res = 0;
    for (int i = 1, j = n; i <= n; i ++)
    {
        while (j && a[j] < i) j --;
        if (a[i] >= i - 1 && i <= m + j)
            res = i;
    }

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 3370. 牛年

4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

unordered_map<string, int> id = {
    {"Ox", 0}, {"Tiger", 1}, {"Rabbit", 2},
    {"Dragon", 3}, {"Snake", 4}, {"Horse", 5}, 
    {"Goat", 6}, {"Monkey", 7}, {"Rooster", 8}, 
    {"Dog", 9}, {"Pig", 10}, {"Rat", 11}
};


int main()
{
    unordered_map<string, int> p;
    p["Bessie"] = 0;

    int n;
    cin >> n;
    while (n -- )
    {
        string s[8];
        for (int i = 0; i < 8; i ++ ) cin >> s[i];

        if (s[3] == "previous")
        {
            int x = p[s[7]], y = id[s[4]];
            int r = ((x - y) % 12 + 12) % 12;
            if (!r) r = 12;
            p[s[0]] = x - r;
        }
        else
        {
            int x = p[s[7]], y = id[s[4]];
            int r = ((y - x) % 12 + 12) % 12;
            if (!r) r = 12;
            p[s[0]] = x + r;
        }
    }

    cout << abs(p["Elsie"]) << endl;
    return 0;
}


活动打卡代码 AcWing 320. 能量项链

4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;

int n;
int f[N][N];
int w[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> w[i];
        w[i + n] = w[i];
    }

    for (int len = 2; len <= n; len ++)
        for (int l = 1; l + len <= n << 1; l ++)
        {
            int r = l + len;
            for (int k = l + 1; k < r; k ++)
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }

    int res = 0;
    for (int i = 1; i <= n << 1; i ++)
        res = max(res, f[i][i + n]);

    cout << res << endl;
    return 0;
}



活动打卡代码 AcWing 1068. 环形石子合并

4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 410, INF = 0x3f3f3f3f;

int n;
int f[N][N], g[N][N];
int w[N], s[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> w[i];
        w[i + n] = w[i];
    }

    for (int i = 1; i <= n << 1; i ++)
        s[i] = s[i - 1] + w[i];

    memset(f, 0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);

    for (int len = 1; len <= n; len ++)
        for (int l = 1; l + len - 1 < n << 1; l ++)
        {
            int r = l + len - 1;
            if (l == r) f[l][r] = g[l][r] = 0;
            else
            {
                for (int k = l; k < r; k ++)
                {
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                    g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }

    int maxv = -INF, minv = INF;
    for (int i = 1; i <= n; i ++)
    {
        maxv = max(maxv, g[i][i + n - 1]);
        minv = min(minv, f[i][i + n - 1]);
    }

    cout << minv << '\n' << maxv << '\n';
    return 0;
}


活动打卡代码 AcWing 292. 炮兵阵地

4_3
1个月前

取的最大值,不用清空滚动数组,$f[i][a][b]$不用清0相当于$f[i-2][a][b]$的个数,取最大无影响
根据有效状态数$60$还可以再离散化一下,优化空间

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 110, M = 65;

int n, m;
int g[N], cnt[M];
int f[2][M][M];
vector<int> state;
vector<int> head[M];

bool check(int state)
{
    return !(state & state >> 1 || state & state >> 2);
}
int count(int state)
{
    int res = 0;
    while (state) res += state & 1, state >>= 1;
    return res;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j < m; j ++)
        {
            char c;
            cin >> c;
            if (c == 'H') g[i] += 1 << j;
        }

    for (int i = 0, j = 0; i < 1 << m; i ++)
        if (check(i))
        {
            state.push_back(i);
            cnt[j ++] = count(i);
        }

    for (int i = 0; i < state.size(); i ++)
        for (int j = 0; j < state.size(); j ++)
            if (!(state[i] & state[j]))
                head[i].push_back(j);

    for (int i = 1; i <= n + 2; i ++)
        for (int a = 0; a < state.size(); a ++)
            if (!(state[a] & g[i]))
                for (int b: head[a])
                    for (int c: head[b])
                        if (!(state[a] & state[c]))
                            f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][b][c] + cnt[a]);

    cout << f[n + 2 & 1][0][0] << '\n';        
    return 0;
}


活动打卡代码 AcWing 327. 玉米田

4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;

int n, m;
int g[N];
int f[2][M];
vector<int> state;
vector<int> head[M];

bool check(int state)
{
    return !(state & state >> 1);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j < m; j ++)
        {
            int x;
            cin >> x;
            if (!x) g[i] |= 1 << j;
        }

    for (int i = 0; i < 1 << m; i ++)
        if (check(i))
            state.push_back(i);

    for (int a: state)
        for (int b: state)
            if (!(a & b))
                head[a].push_back(b);

    f[0][0] = 1;
    for (int i = 1; i <= n + 1; i ++)
        for (int a: state)
        {
            f[i & 1][a] = 0;
            if (!(a & g[i]))
                for (int b: head[a])
                    f[i & 1][a] = (f[i & 1][a] + f[i - 1 & 1][b]) % mod;
        }

    cout << f[n + 1 & 1][0] << '\n';
    return 0;
}


活动打卡代码 AcWing 1064. 小国王

4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 10, K = 110;

int n, k;
LL f[N][K][M];
int cnt[M];
vector<int> state;
vector<int> head[M];

bool check(int state)
{
    return !(state & state >> 1);
}

int count(int state)
{
    int res = 0;
    for (int i = 0; i < n; i ++)
        res += state >> i & 1;
    return res;
}

int main()
{
    cin >> n >> k;

    for (int i = 0; i < 1 << n; i ++)
        if (check(i))
        {
            state.push_back(i);
            cnt[i] = count(i);
        }

    for (int i = 0; i < state.size(); i ++)
        for (int j = 0; j < state.size(); j ++)
        {
            int a = state[i], b = state[j];
            if ((a & b) == 0 && check(a | b))
                head[i].push_back(j);
        }

    f[0][0][0] = 1;
    for (int i = 1; i <= n + 1; i ++)
        for (int j = 0; j <= k; j ++)
            for (int a = 0; a < state.size(); a ++)
            {
                f[i & 1][j][a] = 0;
                for (int b: head[a])
                {
                    int c = cnt[state[a]];
                    if (j >= c)
                        f[i & 1][j][a] += f[i - 1 & 1][j - c][b];
                }
            }

    cout << f[n + 1 & 1][k][0] << '\n';
    return 0;
}


活动打卡代码 AcWing 1052. 设计密码

4_3
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55, MOD = 1e9 + 7;

int n;
char s[N];
int ne[N], f[N][N];

int main()
{
    cin >> n >> s + 1;
    int m = strlen(s + 1);

    for (int i = 2, j = 0; i <= m; i ++)
    {
        while (j && s[i] != s[j + 1]) j = ne[j];
        if (s[i] == s[j + 1]) j ++;
        ne[i] = j;
    }

    f[0][0] = 1;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            for (int k = 'a'; k <= 'z'; k ++)
            {
                int u = j;
                while (u && s[u + 1] != k) u = ne[u];
                if (s[u + 1] == k) u ++;
                f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;
            }

    int res = 0;
    for (int i = 0; i < m; i ++) res = (res + f[n][i]) % MOD;

    cout << res << '\n';
    return 0;
}


活动打卡代码 AcWing 1058. 股票买卖 V

4_3
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int w[N], f[N][3];

int main()
{
    cin >> n;
    for  (int i = 1; i <= n; i ++)
        cin >> w[i];

    f[0][2] = f[0][1] = -0x3f3f3f3f;
    for (int i = 1; i <= n; i ++)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][2]);
        f[i][1] = max(f[i - 1][0] - w[i], f[i - 1][1]);
        f[i][2] = f[i - 1][1] + w[i];
    }

    cout << max(f[n][0], f[n][2]) << endl;
    return 0;
}