头像

ITNXD


访客:2788

离线:16小时前



ITNXD
17小时前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;

int n;

// 1. 按照区间右端点排序
// 2. 扫描每一个区间
// 2.1 若当前区间已被选过点直接跳过
// 2.2 否则,选择当前区间作为该区间

// 贪心:以右端点排序,当每个区间独立时,选择当前区间时为最优,简单解释,后面的区间的左端点可能比当前区间右端点靠前或靠后,但选择当前区间右端点,则重复区间就会被过滤掉
// 按照夹逼定理来证明 res 为最终答案 cnt 为我们按照当前贪心思路算出来的答案
// 1. res <= cnt  反证法:没太听明白。。。
// 2. res >= cnt  若想选区间则一定是贪心的2.1的情况,则说明选区间的情况为区间之间两两不重合的区间,并且我们选择当前区间,不相交,则要将每个区间都选一次,由于res为最大区间数,cnt可能不是最优解,即res >= cnt
// 因此得证:res = cnt

struct Range{
    int l, r;
    bool operator < (const Range & w){
        return r < w.r;
    }
}range[N];

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;
    sort(range, range + n);
    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i++)
        if(range[i].l > ed)
            res ++, ed = range[i].r;

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


活动打卡代码 AcWing 905. 区间选点

ITNXD
17小时前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;

int n;

// 1. 按照区间右端点排序
// 2. 扫描每一个区间
// 2.1 若当前区间已被选过点直接跳过
// 2.2 否则,选择当前区间右端点作为该点

// 贪心:以右端点排序,选择每个区间的右端点时为最优,简单解释,后面的区间的左端点可能比当前区间右端点靠前或靠后,但选择当前区间右端点会最大限度的接近后面区间,为最优值
// 按照夹逼定理来证明 res 为最终答案 cnt 为我们按照当前贪心思路算出来的答案
// 1. res <= cnt  很明显,若我们得到的答案可能不是最优解,则最终答案res要小于等于cnt
// 2. res >= cnt  若想选点则一定是贪心的2.1的情况,则说明选点的情况为区间之间两两不重合的区间,并且我们选择每个区间的右端点,若要将每个区间覆盖则至少需要cnt个点,即res >= cnt
// 因此得证:res = cnt

struct Range{
    int l, r;
    bool operator < (const Range & w){
        return r < w.r;
    }
}range[N];

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;
    sort(range, range + n);
    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i++)
        if(range[i].l > ed)
            res ++, ed = range[i].r;

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


活动打卡代码 AcWing 901. 滑雪

ITNXD
1天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 310;

int n, m, h[N][N], f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

// 记忆化搜索:f[i][j]若是计算过直接返回即可,可以不用继续向下递归
// f[i][j]表示从[i, j]为起点开始走的路径的最长路径
// f[i][j] = max(f[i][j - 1], f[i][j + 1], f[i - 1][j], f[i + 1][j]);

int dp(int x, int y){
    // 算过直接返回
    if(f[x][y] != -1) return f[x][y];
    // 初始化为一个方格为 1
    f[x][y] = 1;
    for(int i = 0; i < 4; i++){
        int a = x + dx[i], b = y + dy[i];
        // 在范围内且高度要低才能往下滑动
        if(a >= 0 && a < n && b >= 0 && b < m && h[a][b] < h[x][y])
            f[x][y] = max(f[x][y], dp(a, b) + 1);
    }
    return f[x][y];
}

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

    // -1表示当前位置没有算过
    memset(f, -1, sizeof f);

    // 枚举每个点开始的长度
    int res = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            res = max(res, dp(i, j));

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



ITNXD
1天前

简单注释题解记录学习

参考代码:

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

using namespace std;
const int N = 6010;

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

// f[u][0]:表示所有以编号u为根的子树中选择并且不选u的方案中的最大值
// f[u][1]:表示所有以编号u为根的子树中选择并且选择u的方案的最大值

// 要保证没有直接上司,也就是说根节点若选,他的儿子就不能选,根节点若不选,他的儿子可选可不选

// f[u][0] += max(f[i][0], f[i][1]); 根节点不选择,则他的儿子可选可不选,则从选与不选挑一个较大值将所有儿子累计起来
// f[u][1] += f[i][0]; 根节点选择,则他的儿子一定不能选,则将所有儿子不选的情况加起来即可

// 树形DP
// 时间复杂度:会发现dfs只会将所有边遍历一遍 为O(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; 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 h);
    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
    dfs(root);
    // 最后答案就是根节点选与不选的两种情况的最大值
    cout << max(f[root][0], f[root][1]) << endl;
    return 0;
}



ITNXD
2天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 6010;

int e[N], h[N], ne[N], idx;
int n, happy[N], 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; 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 h);
    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]) << endl;
    return 0;
}


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

ITNXD
2天前
#include<iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 20, M = 1 << N;

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

// 时间复杂度:1 << n * n * n = 1e6 * 20 * 20 = 4e8

// f[i][j]:表示当前已走的点的状态i且终点是j的所有路径的最短路
// 考虑终点前一个到达的点k:f[i][j] = min(f[i][j], f[1 - (1 << j)][k] + w[k][j]);

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位开始走终点为0的最短距离为 0 
    f[1][0] = 0;
    for(int i = 0; i < 1 << n; i++)
        for(int j = 0; j < n; j++)
            if(i >> j & 1)
                for(int k = 0; k < n; k++)
                    if(i - (1 << j) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

    // (1 << n)  - 1 表示0 ~ n - 1位都是1
    // 结果为:0 ~ n - 1都走过,并且终点为n - 1的最短距离
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}



ITNXD
2天前

简单题解:

参考代码:

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

using namespace std;
const int N = 20, M = 1 << N;

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

// 时间复杂度:1 << n * n * n = 1e6 * 20 * 20 = 4e8

// f[i][j]:表示当前已走的点的状态i且终点是j的所有路径的最短路
// 考虑终点前一个到达的点k:f[i][j] = min(f[i][j], f[1 - (1 << j)][k] + w[k][j]);

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位开始走终点为0的最短距离为 0 
    f[1][0] = 0;
    for(int i = 0; i < 1 << n; i++)
        for(int j = 0; j < n; j++)
            if(i >> j & 1)
                for(int k = 0; k < n; k++)
                    if(i - (1 << j) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

    // (1 << n)  - 1 表示0 ~ n - 1位都是1
    // 结果为:0 ~ n - 1都走过,并且终点为n - 1的最短距离
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}



ITNXD
2天前

自我认为写的还算通俗易懂

关于捅出来:由于定义的是横着摆放的小矩形,上一列有会导致将下一列的该位置占用掉

参考代码:

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

using namespace std;
const int N = 12, M = 1 << N;

int n, m;

// 转态压缩DP
// 时间复杂度:11 * 1 << 11 * 1 << 11 = 10 * 2000 * 2000 = 4e7

// 结论:如果将横着的小矩形摆放完毕(横着摆的矩形要满足两个条件,才能使得合法且竖着的空的位置可以摆放竖着的小矩形以及两个横着的不会冲突),则剩下的矩形只能竖着摆放,且摆放方式唯一
// 1. 对于当前列i来说,如果第i列的当前位置被第i - 1列横着摆的桶了出来而占用,并且第i - 1列的当前位置被第i - 2列横着摆的桶了出来而占用,会发现,第i - 1列的当前位置是两个1 * 1小矩形的覆盖,不符合合法情况
// 2. 要想保证横着摆放完,剩下用来摆放竖着的矩形的位置可以合法摆放,得使得每一列的连续的空的位置为偶数才可以合法摆放
// 对于两种情况用代码表示如下:j 表示当前列的转态, k 表示上一列的状态
// 1. j & k == 0 表示没有冲突
// 2. st[j | k] == true 表示当前转态下没有奇数连续的情况,为合法情况

// f[i][j]:表示第i列(0 ~ n - 1)的j状态(二进制表示范围为1 << n,二进制的第k位为1表示上一列横着摆的的小矩形捅了出来,则会造成当前列该位置被占用),值表示当前状态的总方案数

// 结果很大,用long long来存储
long long f[N][M];
// 表示当前状态下是否有奇数个连续空位 没有为true 有为false
bool st[M];

int main(){
    // 简单的逗号表达式 0 0 时退出
    while(cin >> n >> m, n || m){
        // 预处理st数组
        for(int i = 0; i < 1 << n; i++){
            int cnt = 0;
            st[i] = true;
            for(int j = 0; j < n; j++){
                // 处理两个1之间的0的个数
                if(i >> j & 1){
                    if(cnt & 1) st[i] = false;
                    cnt = 0;
                }else cnt ++;
            }
            // 处理最后一次统计
            if(cnt & 1) st[i] = false;
        }

        memset(f, 0, sizeof f);
        // 初始化:f[0][0]表示第0列没有被捅出来的情况下的方案数,很明显,第一列只能竖着放,方案数唯一,所以为1
        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++)
                    // 两个条件合法才是合法方案
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];

        // 最终答案:应该为m - 1列,但是为了满足最后一列不能捅出来,可以使得最后一列的下一列转态为0即可
        cout << f[m][0] << endl;
    }
    return 0;
}



ITNXD
3天前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 12, M = 1 << N;

int n, m;
long long f[N][M];
// 表示当前状态下是否有奇数个连续空位 没有为true 有为false
bool st[M];

int main(){
    while(cin >> n >> m, n || m){
        // 预处理st数组
        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;
                    cnt = 0;
                }else cnt ++;
            }
            if(cnt & 1) st[i] = false;
        }

        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(int k = 0; k < 1 << n; k++)
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        cout << f[m][0] << endl;
    }
    return 0;
}



ITNXD
4天前

朴素完全背包求解:

参考代码:

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, f[N][N];

// 完全背包求解:
// 1,2,3 ... n 可以看成n个物品的体积,此n个物品的选择无次数限制,背包体积为n,该问题变为了从n个物品中选(可选无限次)使得背包体积恰好为n的选法

// f[i][j]:表示从前i个物品中选使得体积恰好等于j的选法
// 考虑最后一步i的选择个数
// f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] ... f[i - 1][j - s * i] (s * i <= j)
// f[i][j - i] =           f[i - 1][j - i] + f[i - 1][j - 2 * i] ... f[i - 1][j - s * i]
// 化解得:f[i][j] = f[i - 1][j] + f[i][j - i];

int main(){
    cin >> n;
    // 前0个物品不选使体积为0的选法为 1 (不选也是一种选法)f[0][j] = 0 (无法从前0个物品选使得体积为j,不选也不行)
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= n; j++)
            if(j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
            else f[i][j] = f[i - 1][j] % mod;

    cout << f[n][n] << endl;
    return 0;
}

二进制优化空间版本

自认为这样写比压缩为一维更好理解

参考代码:

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, f[2][N];

// 完全背包求解:
// 1,2,3 ... n 可以看成n个物品的体积,此n个物品的选择无次数限制,背包体积为n,该问题变为了从n个物品中选(可选无限次)使得背包体积恰好为n的选法

// f[i][j]:表示从前i个物品中选使得体积恰好等于j的选法
// 考虑最后一步i的选择个数
// f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] ... f[i - 1][j - s * i] (s * i <= j)
// f[i][j - i] =           f[i - 1][j - i] + f[i - 1][j - 2 * i] ... f[i - 1][j - s * i]
// 化解得:f[i][j] = f[i - 1][j] + f[i][j - i];

int main(){
    cin >> n;
    // 前0个物品不选使体积为0的选法为 1 (不选也是一种选法)f[0][j] = 0 (无法从前0个物品选使得体积为j,不选也不行)
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= n; j++)
            if(j >= i) f[i & 1][j] = (f[i - 1 & 1][j] + f[i & 1][j - i]) % mod;
            else f[i & 1][j] = f[i - 1 & 1][j] % mod;

    cout << f[n & 1][n] << endl;
    return 0;
}

一维压缩版本

参考代码:

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, f[N];

int main(){
    cin >> n;
    // 体积为0的选法为1(即都不选择)
    f[0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            // f[i][j] = f[i - 1][j] + f[i][j - i];
            // 对于f[i - 1][j]:很明显就是将上一层的f[i]赋值到了本层,不需要其他处理
            // 对于j - i:j - i < j 即从前往后算j - i 一定会先算,计算的就是f[i][j - 1]的情况
            f[j] = (f[j] + f[j - i]) % mod;

    cout << f[n] << endl;
    return 0;
}

换一种思路:奇葩思路(很难想到)

转移方程也不好考虑,以及集合划分不好想

参考代码:

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, f[N][N];

// f[i][j]:表示总和为i,恰好选了j个数的方案数
// 集合分为两类:选了1 / 没选1 (奇葩思路)
// 1. 选了1,去掉一个1,f[i - 1][j - 1]
// 2. 没选1,则将j个数都减去1,f[i - j][j] (奇葩思路)

int main(){
    cin >> n;
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
    // j <= i 才会使得集合的两部分合法,不重不漏,选1和不选1
        for(int j = 1; j <= i; j++)
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

    int res = 0;
    for(int i = 1; i <= n; i++) res = (res + f[n][i]) % mod;
    cout << res << endl;
    return 0;
}