个人空间 - AcWing

eric_fyq

$\href{网址}{\color{black}{更新信息}}$

关注数

粉丝数

阅读量

7383

+关注发消息

在线

最近来访(278)

ssy_

太阳下山了吗

bline

Pedantry

Kazimierz

如许

六柒

_beta

不止于此

1967891554

NNNN-----IIII

lindi530

莫德歪奇

面包面包

0x3F3F3F3F3F3F3F3F

卤化氢

有机物

WA-TLE

rzybzzzz

小蝴蝶

活动打卡代码 AcWing 285. 没有上司的舞会

eric_fyq
20小时前

                根据father的状态来确定转移方程，第一种：如果父类为1，那么子类只有为0，那么此时枚举所有的子类，然后父类加上最大子类的值。第二种：父类为0，那么父类需要加上所有子类（有0和1两种状态）两种状态中最大的
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 6010;

int e[N], ne[N], h[N], idx;
int n, happy[N];
bool has_father[N];
int f[N][2];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);

        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}

int main()
{
    cin >> n;
    //读入happy[i]
    for(int i = 1; i <= n; i ++) scanf("%d", &happy[i]);

    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i ++)
    {
        int l, k;
        scanf("%d%d", &l, &k);
        add(k, l);
        has_father[l] = true;
    }

    int root = 1;
    while(has_father[root]) root ++;

    dfs(root);

    int res = 0;
    res = max(f[root][0], f[root][1]);

    cout << res << endl;

    return 0;
}

            

活动打卡代码 AcWing 901. 滑雪

eric_fyq
22小时前

                滑雪最暴力做法bfs  过了9/12个点，做法不可取
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define x first
#define y second

using namespace std;

const int N = 310;
typedef pair<int, int> PII;

int g[N][N], dist[N][N];
int n, m;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};


void bfs(int st, int ed)
{
    queue<PII> q;
    q.push({st, ed});

    while(q.size())
    {
        PII t = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++)
        {
            int xx = t.x + dx[i];
            int yy = t.y + dy[i];
            if(xx >= 0 && xx < n && yy >= 0 && yy < m &&
             g[xx][yy] < g[t.x][t.y])
             {
                 dist[xx][yy] = max(dist[t.x][t.y] + 1, dist[xx][yy]);
                 q.push({xx, yy});
             }
        }
    }
}

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

    //输入地图
    for(int i = 0; i < n; i ++) 
        for(int j = 0; j < m; j ++)
            scanf("%d", &g[i][j]);

    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
           bfs(i, j);

    int res = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
           res = max(res, dist[i][j]);

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


最终做法使用dfs记忆化搜索
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 310;

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

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; 

int dp(int x, int y)
{
    int &v = f[x][y];
    if(v != -1) return v;

    v = 1;
    for(int i = 0; i < 4; i ++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] < g[x][y])
            v = max(v, dp(xx, yy) + 1);
    }
    return v;
}

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

    //输入每个滑雪场的高度
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d", &g[i][j]);

    memset(f, -1, sizeof f);

    int res = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            res = max(res, dp(i, j));

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

            

活动打卡代码 AcWing 900. 整数划分

eric_fyq
23小时前

                #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n, f[N];

int main()
{
    cin >> n;
    f[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i; j <= n; j ++)
        {
            f[j] = (f[j] + f[j - i]) % mod;
        }
    }
    cout << f[n] << endl;
    return 0;
}

            

活动打卡代码 AcWing 282. 石子合并（算法基础课）

eric_fyq
1天前

                #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 310;

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

int main()
{
    cin >> n;
    //求出前n堆石子的前缀和
    for(int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        s[i] += s[i-1];
    }

    for(int len = 2; len <= n; len ++)//枚举区间长度
    {
        for(int i = 1; i + len - 1 <= n; i ++)//枚举区间起点
        {
            int j = i + len - 1;
            f[i][j] = 2e9;
            for(int k = i; k < j; k ++)//枚举区间分隔线
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1]);
            }
        }
    }
    cout << f[1][n] << endl;
    return 0;
}

            

活动打卡代码 AcWing 282. 石子合并

eric_fyq
1天前

                #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 310;

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

int main()
{
    cin >> n;
    //求出前n堆石子的前缀和
    for(int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        s[i] += s[i-1];
    }

    for(int len = 2; len <= n; len ++)//枚举区间长度
    {
        for(int i = 1; i + len - 1 <= n; i ++)//枚举区间起点
        {
            int j = i + len - 1;
            f[i][j] = 2e9;
            for(int k = i; k < j; k ++)//枚举区间分隔线
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i-1]);
            }
        }
    }
    cout << f[1][n] << endl;
    return 0;
}

            

活动打卡代码 AcWing 893. 集合-Nim游戏（算法基础课）

eric_fyq
1天前

                #include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 110;

int n, k, f[100010], s[N];
int res;

int sg(int x)
{
    if(f[x] != -1) return f[x];

    unordered_set<int> S;
    for(int i = 1; i <= k; i ++)
    {
        int num = s[i];
        if(x >= num) S.insert(sg(x - num));
    }

    for(int i = 0; ; i ++)
    {
        if(S.count(i) == 0) return f[x] = i;
    }
}

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

    memset(f, -1, sizeof f);
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

            

活动打卡代码 AcWing 891. Nim游戏（算法基础课）

eric_fyq
2天前

                #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int n, x, res;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> x;
        res ^= x;
    }
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

            

活动打卡代码 AcWing 897. 最长公共子序列（算法基础课）

eric_fyq
2天前

                #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1010;

char a[N], b[N];
int n, m;
int f[N][N];

int main()
{
    cin >> n >> m >> a + 1 >> b + 1;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
            if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
        }
    }
    cout << f[n][m] << endl;

    return 0;
}

            

活动打卡代码 AcWing 895. 最长上升子序列（算法基础课）

eric_fyq
2天前

                #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);

    for(int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        for(int j = 1; j < i; j ++)
        {
            if(w[j] < w[i])
            {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    int maxv = 0;
    for(int i = 1; i <= n; i ++)
    {
        maxv = max(maxv, f[i]);
    }
    cout << maxv << endl;

    return 0;
}

            

活动打卡代码 AcWing 898. 数字三角形（算法基础课）

eric_fyq
2天前

                #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 5010, M = 510;

int f[M][N], n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= i; j ++)
        {
            scanf("%d", &f[i][j]);
        }
    }

    for(int i = n-1; i >= 1; i --)
    {
        for(int j = 1; j <= n; j ++)
        {
            f[i][j] = max(f[i][j] + f[i+1][j], f[i][j] + f[i+1][j+1]);
        }
    }
    cout << f[1][1] << endl;
    return 0;
}

            

根据father的状态来确定转移方程，第一种：如果父类为1，那么子类只有为0，那么此时枚举所有的子类，然后父类加上最大子类的值。第二种：父类为0，那么父类需要加上所有子类（有0和1两种状态）两种状态中最大的

0 评论

滑雪最暴力做法bfs 过了9/12个点，做法不可取

最终做法使用dfs记忆化搜索

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论