rushhhhh

关注数

粉丝数

阅读量

763

+关注发消息

离线：4小时前

题解 AcWing 285. 没有上司的舞会

rushhhhh
5小时前

                #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
状态表示f[i,0], f[i,1]
    集合：（用0、1表示）邀请/不邀请i号职员参加舞会
    属性：max
状态计算
    不选i，则f[i,0] += max(f[s,0], f[s,1])
        其中，遍历所有子结点。子结点当然可选可不选，故取其max
    选i，则f[i,1] += f[s,0]
        同样遍历所有子结点。子结点只能不选（因为父结点i选了）
*/
const int N = 6010;
int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N];

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][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

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

    memset(h, -1, sizeof(f));
    for(int i=0; i < n-1; i++)
    {
        int a, b;
        cin >> a >> b;
        has_father[a] = true;
        add(b, a);
    }

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

    dfs(root);

    cout << max(f[root][0], f[root][1]);
}

            

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

rushhhhh
5小时前

                #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
状态表示f[i,0], f[i,1]
    集合：（用0、1表示）邀请/不邀请i号职员参加舞会
    属性：max
状态计算
    不选i，则f[i,0] += max(f[s,0], f[s,1])
        其中，遍历所有子结点。子结点当然可选可不选，故取其max
    选i，则f[i,1] += f[s,0]
        同样遍历所有子结点。子结点只能不选（因为父结点i选了）
*/
const int N = 6010;
int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N];

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][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

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

    memset(h, -1, sizeof(f));
    for(int i=0; i < n-1; i++)
    {
        int a, b;
        cin >> a >> b;
        has_father[a] = true;
        add(b, a);
    }

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

    dfs(root);

    cout << max(f[root][0], f[root][1]);
}

            

活动打卡代码 AcWing 91. 最短Hamilton路径

rushhhhh
14小时前

                #include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
状态表示f[i,j]
    集合：经过i表示的结点，从0到j的所有路径
    属性：最小值
状态计算
    把每条路径不重不漏地分类，可以这么分：
    枚举每条路径的倒数第二个结点，例如：
    0-j可分为倒数第二个结点是
    0、1、2、...、n-1
    若此结点是k，则
    路径分划分为0->k->j，其中k->j = w[k][j]
    而0->k则等于f[i-{j}][k]
    即所有从0到k，经过结点为i（二进制）除去j的路径
*/
const int N = 21, M = 1<<N;
int n;
int w[N][N], f[M][N];

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

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;

    for(int i=0; i < 1<<n; i++)
        for(int j=0; j<n; j++)
            // 判断路径是否合法（j结点是否在i表示的集合中）
            if(i>>j & 1)
                // 枚举倒数第二个结点
                for(int k=0; k<n; k++)
                    // 判断路径是否合法（k结点是否在i表示的集合中）
                    if(i>>k & 1)
                        f[i][j] = min(f[i][j], f[i-(1<<j)][k] + w[k][j]);

    // 不重不漏地经过每个点恰好一次，所以i是111111
    cout << f[(1<<n)-1][n-1];
}

            

题解 AcWing 91. 最短Hamilton路径

rushhhhh
14小时前

                #include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
状态表示f[i,j]
    集合：经过i表示的结点，从0到j的所有路径
    属性：最小值
状态计算
    把每条路径不重不漏地分类，可以这么分：
    枚举每条路径的倒数第二个结点，例如：
    0-j可分为倒数第二个结点是
    0、1、2、...、n-1
    若此结点是k，则
    路径分划分为0->k->j，其中k->j = w[k][j]
    而0->k则等于f[i-{j}][k]
    即所有从0到k，经过结点为i（二进制）除去j的路径
*/
const int N = 21, M = 1<<N;
int n;
int w[N][N], f[M][N];

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

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;

    for(int i=0; i < 1<<n; i++)
        for(int j=0; j<n; j++)
            // 判断路径是否合法（j结点是否在i表示的集合中）
            if(i>>j & 1)
                // 枚举倒数第二个结点
                for(int k=0; k<n; k++)
                    // 判断路径是否合法（k结点是否在i表示的集合中）
                    if(i>>k & 1)
                        f[i][j] = min(f[i][j], f[i-(1<<j)][k] + w[k][j]);

    // 不重不漏地经过每个点恰好一次，所以i是111111
    cout << f[(1<<n)-1][n-1];
}

            

题解 AcWing 275. 传纸条

rushhhhh
2天前

参考：

AcWing 275. 证明传纸条为何可以使用方格取数的代码
 AcWing 275. 传纸条

#include <iostream>
using namespace std;

const int N = 51;
int m, n;
int x, y, w;
int g[N][N];
int f[N*2][N][N];

const int N = 51;
int m, n;
int x, y, w;
int g[N][N];
int f[N*2][N][N];

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

    for(int k=2; k<=n+m; k++)
        for(int j=1; j<=n; j++)
            for(int b=1; b<=n; b++)
            {
                int i = k-j, a = k-b;
                if(i>=1 && i<=m && a>=1 && a<=m)
                {
                    f[k][j][b] = max(max(f[k-1][j][b], f[k-1][j-1][b]),
                                     max(f[k-1][j][b-1], f[k-1][j-1][b-1]));
                    if(j == b)
                        f[k][j][b] += g[i][j];
                    else
                        f[k][j][b] += (g[i][j] + g[a][b]);
                }
            }
    cout << f[n+m][n][n];

}

题解 AcWing 1027. 方格取数

rushhhhh
2天前

                #include <iostream>
#include <vector>
using namespace std;
/*
状态表示f[i,j,a,b]
    集合
        P1走到[i,j]，P2走到[a,b]的路径
    属性
        最大值
状态计算
    f[i-1,j,a-1,b] + c[i,j] + c[a,b]
    f[i-1,j,a,b-1]
    f[i,j-1,a-1,b]
    f[i,j-1,a,b-1]
    特殊情况
        如果[i,j] == [a,b]
        则只算一次c
*/
const int N = 11;
int n;
int x, y, w;
int g[N][N];
int f[N][N][N][N];

int main()
{
    cin >> n;
    while(cin >> x >> y >> w, x||y||w)
        g[x][y] = w;

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

}

            

题解 AcWing 291. 蒙德里安的梦想

rushhhhh
4天前

常规做法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
/*
思想
    先放横着的，再放竖着的
    则总方案数等于只放横着的小方块的合法方案数
    如何判断当前方案是否合法：
        即判断剩余位置是否能填充满竖着的小方块
        因此可以按列来看：每一列内部所有连续的空着的小方块，需要是偶数个
状态表示
    集合表示：
        f[i,j]表示已经将前i-1列摆好，且从第i-1列伸出到第i列的所有方案
        伸出的状态是j（j用二进制表示状态，1表示伸出，0表示没有伸出）
    属性：方案数
状态计算
    f[i][j] += f[i-1][k]
        k从0到2^n
        当且仅当可从k状态转移到j状态
*/

const int N = 12, M = 1<<N;
int n, m;
long long f[N][M];
// st表示状态是否合法
bool st[M];

int main()
{
    while(cin >> n >> m, n||m)
    {
        // 遍历n行每行是否往外伸的所有情况代表的i
        // 比如n==4时，1001合法，1100合法，1011不合法
        for (int i = 0; i < 1<<n; ++i)
        {
            // cnt表示连续空着的方块的长度
            int cnt = 0;
            st[i] = true;
            for(int j=0; j<n; j++)
            {
                // 如果当前这一位即第j位是1
                if(i>>j & 1)
                {
                    // 则判断前面是否有奇数个0
                    if(cnt & 1)
                        st[i] = false;
                    cnt = 0;
                }
                else cnt++;
            }
            // 判断最后剩余的0
            if(cnt & 1)
                st[i] = false;
        }
        // 每组案例重置充值f
        memset(f, 0, sizeof(f));
        // 已经将前-1列摆好，且从第-1列伸出到第0列，
        // 伸出的状态是0的方案只有一种：什么都不放
        f[0][0] = 1;

        // 遍历列
        for(int i=1; i<=m; i++)
            // 遍历当前列的状态
            for(int j=0; j < 1<<n; j++)
                // 遍历上一列的状态
                for(int k=0; k < 1<<n; k++)
                    // 可以从上一列的状态转移到当前j状态
                    // 满足：前后不在同一行；
                    // 注意，&优先级低于==
                    // k表示伸到当前列的状态，j表示伸出当前列的状态
                    // 横着的长方形长度为2，所以要计算二者的并集
                    // 要从k到j合法，则都伸后当前列连续0个数要时偶数，即st==true
                    if((j&k)==0 && st[j|k])
                        f[i][j] += f[i-1][k];
        // 棋盘下标从0开始，前m列已经摆好，则第m列的状态0
        // （即什么都没伸到第m列）的方案数即为所求
        cout << f[m][0] << endl;
    }
}

优化做法

先把所有合法转移存储起来

 #include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 12, M = 1<<N;
int n, m;
long long f[N][M];
// state[j]表示所有能转移到j的合法状态有哪些
vector<int> state[M];
bool st[M];

int main()
{
    while(cin >> n >> m, n||m)
    {
        for (int i = 0; i < 1<<n; ++i)
        {
            int cnt = 0;
            st[i] = true;
            for(int j=0; j<n; j++)
                if(i>>j & 1)
                {
                    if(cnt & 1)
                    {
                        st[i] = false;
                        break;
                    }
                    cnt = 0;
                }
                else cnt++;
            if(cnt & 1)
                st[i] = false;
        }

        for(int i=0; i < 1<<n; i++)
        {
            state[i].clear();
            for(int j=0; j < 1<<n; j++)
                if((i&j) == 0 && st[i|j])
                    state[i].push_back(j);
        }

        memset(f, 0, sizeof(f));
        f[0][0] = 1;

        for(int i=1; i<=m; i++)
            for(int j=0; j < 1<<n; j++)
                for(auto k : state[j])
                    f[i][j] += f[i-1][k];
        cout << f[m][0] << endl;
    }
}

活动打卡代码 AcWing 291. 蒙德里安的梦想

rushhhhh
4天前

常规做法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
/*
思想
    先放横着的，再放竖着的
    则总方案数等于只放横着的小方块的合法方案数
    如何判断当前方案是否合法：
        即判断剩余位置是否能填充满竖着的小方块
        因此可以按列来看：每一列内部所有连续的空着的小方块，需要是偶数个
状态表示
    集合表示：
        f[i,j]表示已经将前i-1列摆好，且从第i-1列伸出到第i列的所有方案
        伸出的状态是j（j用二进制表示状态，1表示伸出，0表示没有伸出）
    属性：方案数
状态计算
    f[i][j] += f[i-1][k]
        k从0到2^n
        当且仅当可从k状态转移到j状态
*/

const int N = 12, M = 1<<N;
int n, m;
long long f[N][M];
// st表示状态是否合法
bool st[M];

int main()
{
    while(cin >> n >> m, n||m)
    {
        // 遍历n行每行是否往外伸的所有情况代表的i
        // 比如n==4时，1001合法，1100合法，1011不合法
        for (int i = 0; i < 1<<n; ++i)
        {
            // cnt表示连续空着的方块的长度
            int cnt = 0;
            st[i] = true;
            for(int j=0; j<n; j++)
            {
                // 如果当前这一位即第j位是1
                if(i>>j & 1)
                {
                    // 则判断前面是否有奇数个0
                    if(cnt & 1)
                        st[i] = false;
                    cnt = 0;
                }
                else cnt++;
            }
            // 判断最后剩余的0
            if(cnt & 1)
                st[i] = false;
        }
        // 每组案例重置充值f
        memset(f, 0, sizeof(f));
        // 已经将前-1列摆好，且从第-1列伸出到第0列，
        // 伸出的状态是0的方案只有一种：什么都不放
        f[0][0] = 1;

        // 遍历列
        for(int i=1; i<=m; i++)
            // 遍历当前列的状态
            for(int j=0; j < 1<<n; j++)
                // 遍历上一列的状态
                for(int k=0; k < 1<<n; k++)
                    // 可以从上一列的状态转移到当前j状态
                    // 满足：前后不在同一行；
                    // 注意，&优先级低于==
                    // k表示伸到当前列的状态，j表示伸出当前列的状态
                    // 横着的长方形长度为2，所以要计算二者的并集
                    // 要从k到j合法，则都伸后当前列连续0个数要时偶数，即st==true
                    if((j&k)==0 && st[j|k])
                        f[i][j] += f[i-1][k];
        // 棋盘下标从0开始，前m列已经摆好，则第m列的状态0
        // （即什么都没伸到第m列）的方案数即为所求
        cout << f[m][0] << endl;
    }
}

优化做法

先把所有合法转移存储起来

 #include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 12, M = 1<<N;
int n, m;
long long f[N][M];
// state[j]表示所有能转移到j的合法状态有哪些
vector<int> state[M];
bool st[M];

int main()
{
    while(cin >> n >> m, n||m)
    {
        for (int i = 0; i < 1<<n; ++i)
        {
            int cnt = 0;
            st[i] = true;
            for(int j=0; j<n; j++)
                if(i>>j & 1)
                {
                    if(cnt & 1)
                    {
                        st[i] = false;
                        break;
                    }
                    cnt = 0;
                }
                else cnt++;
            if(cnt & 1)
                st[i] = false;
        }

        for(int i=0; i < 1<<n; i++)
        {
            state[i].clear();
            for(int j=0; j < 1<<n; j++)
                if((i&j) == 0 && st[i|j])
                    state[i].push_back(j);
        }

        memset(f, 0, sizeof(f));
        f[0][0] = 1;

        for(int i=1; i<=m; i++)
            for(int j=0; j < 1<<n; j++)
                for(auto k : state[j])
                    f[i][j] += f[i-1][k];
        cout << f[m][0] << endl;
    }
}

题解 AcWing 1012. 友好城市

rushhhhh
5天前

                #include <iostream>
#include <algorithm>
using namespace std;

const int N = 5010;

struct tmp
{
    int a, b;
}s[N];

bool cmp(tmp t1, tmp t2)
{
    if(t1.a < t2.a)
        return true;
    else
        return false;
}

int n;
int f[N];

int main()
{
    cin >> n;

    for(int i=0; i<n; i++)
    {
        f[i] = 1;
        cin >> s[i].a >> s[i].b;
    }

    sort(s, s+n, cmp);

    for(int i=0; i<n; i++)
        for(int j=0; j<i; j++)
            if(s[i].b > s[j].b)
                f[i] = max(f[i], f[j]+1);

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

    return 0;
}

            

题解 AcWing 1016. 最大上升子序列和

rushhhhh
5天前

                #include <iostream>
using namespace std;
/*
状态表示f[i]
    集合：以f[i]结尾的上升子序列的和
    属性：最大值，max
状态计算
    if(a[i] > a[j])
        f[i] = max(f[j], a[i] + f[j])
*/


const int N = 1010;
int n;
int f[N], a[N];

int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> a[i];
        f[i] = a[i];
    }

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

            

0 评论

0 评论

0 评论

0 评论

参考：

0 评论

0 评论

常规做法

优化做法

0 评论

常规做法

优化做法

0 评论

0 评论

0 评论