头像

kuan525

武汉轻工大学算法协会




离线:4小时前


最近来访(179)
用户头像
坠明
用户头像
嘉然今天吃什么.
用户头像
星月夜
用户头像
sssz
用户头像
自然卷_6
用户头像
HUE_SC
用户头像
Ncik
用户头像
dawnsinky
用户头像
SanShi
用户头像
指的就是你
用户头像
L.妍ab
用户头像
理想世界
用户头像
XCX
用户头像
俄罗斯刺沙蓬
用户头像
糕小芝
用户头像
Vanish_7
用户头像
只吃虾仁大雪菜
用户头像
Kiribati
用户头像
咖喱鸡排饭
用户头像
Cyzh


kuan525
2天前
#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int v[N][N];

void slove()
{
    int n, m; scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            scanf("%d", &v[i][j]);
            v[i][j] += max(v[i][j-1], v[i-1][j]);
        }
    cout << v[n][m] << endl;
}

int main()
{
    int tt; cin >> tt;
    while(tt --){
        slove();
    }

    return 0;
}



kuan525
3天前

f[k][i][j]:当前两个点的x+y等于k,第一个点x为i,第二个点x为j
本题可以转化为从左上角往右下角同时传两个纸条,在传输过程中没有交点,所以可以dp为两个点的位置

所以有状态转移方程为:

if(i != j) //当前状态的两个点没有重合
    for(int a = 0; a <= 1; a ++)//可能存在有i-a == j-b的情况,这种情况f一定为0,所以不会是max
        for(int b = 0; b <= 1; b ++)
            f[k][i][j] = max(f[k][i][j], f[k-1][i-a][j-b] + w[i][k-i] + w[j][k-j]);
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;
int w[N][N], f[2*N][N][N];//f[k][i][j]:当前两个点的x+y等于k,第一个点x为i,第二个点x为j
int n, m;

int main()
{
    cin >> m >> n;
    //memset(w, 128, sizeof w);
    for(int i = 1; i <= m; i ++)
        for(int j = 1; j <= n; j ++)
            scanf("%d", &w[i][j]);

    // 1 <= i <= m     1 <= k-i <= n   ---->  max(1, k-n) <= i <= min(m, k-1);
    // 1 <= j <= m     1 <= k-j <= n   ---->  max(1, k-n) <= j <= min(m, k-1);
    //两个人同时从(1, 1)出发
    for(int k = 2; k <= n + m; k ++)
        for(int i = max(1, k-n); i <= min(m, k-1); i ++)
            for(int j = max(1, k-n); j <= min(m, k-1); j ++)
            {
                //当前状态可以从四种状态转移过来,同时那四种状态的i+j一定小于k,所以一定被遍历过
                if(i != j) //当前状态的两个点没有重合
                    for(int a = 0; a <= 1; a ++)//可能存在有i-a == j-b的情况,这种情况f一定为0,所以一定不会是max
                        for(int b = 0; b <= 1; b ++)
                            f[k][i][j] = max(f[k][i][j], f[k-1][i-a][j-b] + w[i][k-i] + w[j][k-j]);
            }

    cout << f[n+m-1][m][m-1] << endl;

    return 0;
}



kuan525
5天前

f[a][b][c][d]表示当前使用a张1,b张2,c张3,d张4 的最大价值
可以从前四种状态转移过来,状态转移方程见代码
初始化第一个点即可

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

using namespace std;

const int N = 41, M = 360;
int q[M], w[5], f[N][N][N][N];//当前使用a张1,b张2,c张3,d张4 的最大价值

int main()
{
    int n, m, a; cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> q[i];
    for(int i = 1; i <= m; i ++) {cin >> a; w[a] ++;}

    f[0][0][0][0] = q[0];//第一个点的权值
    for(int A = 0; A <= w[1]; A ++)
        for(int B = 0; B <= w[2]; B ++)
            for(int C = 0; C <= w[3]; C ++)
                for(int D = 0; D <= w[4]; D ++)
                {
                    int d = A*1 + B*2 + C*3 + D*4;//当前在什么位置
                    int &t = f[A][B][C][D];

                    if(A) t = max(t, f[A-1][B][C][D] + q[d]);
                    if(B) t = max(t, f[A][B-1][C][D] + q[d]);
                    if(C) t = max(t, f[A][B][C-1][D] + q[d]);
                    if(D) t = max(t, f[A][B][C][D-1] + q[d]);
                }

    cout << f[w[1]][w[2]][w[3]][w[4]] << endl;

    return 0;
}



kuan525
5天前

f[i][j]表示当前在第i位(第0位最小),且后面最多有j个1的方案数

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

using namespace std;
using LL = long long;

const int N = 35;
LL f[N][N], c[N][N];//因为是在32位以内,所以c可以直接使用int,但是f数组是一个累加的过程会爆int,必须使用LL
//f[i][j]表示当前在第i位(第0位最小),且后面最多有j个1的方案数

int main()
{
    LL n, l, m; //长度、1的最大个数、第几个数
    cin >> n >> l >> m;

    //初始化全排列数组,因为数据范围不大,这里直接使用dp预处理所有可能使用到的全排列数
    c[0][0] = 1;
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= i; j ++)
            if(!j) c[i][j] = 1;
            else c[i][j] = c[i-1][j] + c[i-1][j-1];//这里不必担心i=j,因为c[i-1][j-1]被赋值过

    //处理f数组
    for(int i = 0; i <= n; i ++)//当前所在的位数
        for(int j = 0; j <= n; j ++)//当前位数后面1的最大个数,这里一定要到n,因为例如f[2][3]=f[2][2]有意义
            for(int k = 0; k <= j; k ++)//j这个状态可以通过所有k状态推过来
                f[i][j] += c[i][k];

    //开始数位dp
    for(int i = n; i >= 1; i --)//当前讨论第i位是否有1
    {
        if(f[i-1][l] < m){//当前位置为0时,方案数小于m
            cout << 1;
            m -= f[i-1][l];//当前位置是1,所以减去当前不是1的情况且后面满足的情况
            l --;//后面可以使用的1的最大个数减少1
        }
        else cout << 0;
    }

    return 0;
}



kuan525
6天前

见鬼!f数组开小了,未定义的错误真可怕,以后出现一些不可描述的问题就是数组开小了,debug 40分钟

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

using namespace std;

const int N = 13, mod = 1e8;
int f[N][1<<N], q[N];
vector<int> v[13];
int n, m;

bool check(int n){
    int x = n % 2; n /= 2;
    while(n){
        if(x == 1 && x == n % 2) return false;
        x = n % 2; n /= 2;
    }
    return true;
}

int main()
{
    //读入数据
    cin >> n >> m;

    for(int i = 1; i <= n; i ++)
    {
        int tmp = 0;
        for(int j = 1; j <= m; j ++){
            int a; cin >> a;
            tmp = tmp * 2 + !a;
        }
        q[i] = tmp;
        //cout << tmp << endl;
    }

    //预处理满足条件的值, 按照行来算
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j < 1<<m; j ++)
            if((j & q[i]) == 0 && check(j))
                v[i].push_back(j);

    //开始枚举
    for(auto i : v[1]) f[1][i] = 1;

    for(int i = 2; i <= n; i ++)
        for(auto j : v[i])//枚举当前行
            for(auto k : v[i-1])//枚举上一列
                if((j & k) == 0)
                    f[i][j] = (f[i][j] + f[i-1][k]) % mod;

    int ans = 0;   
    for(auto i : v[n]) ans = (ans + f[n][i]) % mod;
    cout << ans << endl;

    return 0;
}



kuan525
9天前

环形结构动态规划

破题口在于如何找到状态表示,首先观察题目,发现制约因素仅仅知识在休息的一段时间里面,第一个小时不算,所以我们可能利用线性dp的思路,找到相邻两项的关系,这里我们用f[i][j][0&1]表示当前在第i个小时,当前以及睡了j个小时,且当前这个小时有没有睡(0 & 1),然后找到相邻两项的递推关系,容易得到:
状态表示
f[i][j][0&1]
属性
max
状态计算
f[i][j][0] = max(f[i-1][j][1], f[i-1][j][0])
f[i][j][1] = max(f[i-1][j-1][1] + w[i], f[i-1][j-1][0])
于是我们便可以开始初始化数据开始dp了,但是我们意识到一个问题,这时候该怎么初始化呢,第一个小时有没有价值,所以我们得到结论,当最后一个小时睡了觉,则第一个小时有效,否则无效,所以我们可以分两部分来dp

//第n小时不睡觉 
memset(f, -0x3f, sizeof f);//初始化为负无穷
f[1][0][0] = f[1][1][1] = 0;

//第n小时睡觉 
memset(f, -0x3f, sizeof f);//初始化为负无穷
f[1][0][0] = 0; f[1][1][1] = w[1];

我们需要开辟一个N的二维空间,但是本题空间有限,所以我们需要采用滚动数组的方式,使用一个新技巧用【&1】来保留最近两层的数据,重复滚动即可,可以自己去行了解

屏幕截图 2021-11-19 192933.png

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

using namespace std;
using LL = long long;

const int N = 4000;
LL f[2][N][2], w[N];
int n, m;

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

    //第n小时不睡觉
    memset(f, -0x3f, sizeof f);//初始化为负无穷
    f[1][0][0] = f[1][1][1] = 0;
    for(int i = 2; i <= n; i ++)
        for(int j = 0; j <= min(i, m); j ++)
        {
            f[i & 1][j][0] = max(f[i-1 & 1][j][1], f[i-1 & 1][j][0]);
            if(j >= 1) f[i & 1][j][1] = max(f[i-1 & 1][j-1][1] + w[i], f[i-1 & 1][j-1][0]);
        }
    LL ans = f[n & 1][m][0];

    //第n小时睡觉
    memset(f, -0x3f, sizeof f);//初始化为负无穷
    f[1][0][0] = 0; f[1][1][1] = w[1];
    for(int i = 2; i <= n; i ++)
        for(int j = 0; j <= min(i, m); j ++)
        {
            f[i & 1][j][0] = max(f[i-1 & 1][j][1], f[i-1 & 1][j][0]);
            if(j >= 1) f[i & 1][j][1] = max(f[i-1 & 1][j-1][1] + w[i], f[i-1 & 1][j-1][0]);
        }
    ans = max(ans, f[n & 1][m][1]);

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 275. 传纸条

kuan525
9天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;  
int v[N][N];
int f[N*2][N][N];

int main()
{
    int m, n; cin >> n >> m; //n行m列

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d", &v[i][j]);

    for(int k = 2; k <= n + m; k ++)
        for(int x1 = max(1, k-m); x1 <= min(n, k-1); x1 ++)
            for(int x2 = max(1, k-m); x2 <= min(n, k-1); x2 ++)
            {
                int t = v[x1][k-x1];
                if(x1 != x2) t += v[x2][k-x2];
                for(int a = 0; a <= 1; a ++)
                    for(int b = 0; b <= 1; b ++)
                        f[k][x1][x2] = max(f[k][x1][x2], f[k-1][x1-a][x2-b] + t);
            }
    cout << f[n+m][n][n] << endl;

    return 0;
}




kuan525
9天前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
using LL = long long;

const int N = 12, M = 1 << N;//这里N要开大一个,因为后面要算到11后面一个位置
LL st[M], f[N][M];
vector<int> state[M];
int n, m;

int main()
{
    while(cin >> n >> m, n || m)//n行m列
    {
        //首先预处理st数组,标记所有状态,看是否满足
        for(int i = 0; i < 1 << n; i ++)
        {
            //遍历所有位
            int cnt = 0;
            bool is_vaule = true;
            for(int j = 0; j < n; j ++)
            {
                if((i >> j & 1)){//当前为1
                    if(cnt & 1){//当前的0已经是奇数
                        is_vaule = false;
                        break;
                    }
                    cnt = 0;
                }
                else cnt ++;
            }
            if(cnt & 1) is_vaule = false;
            st[i] = is_vaule;
        }

        //第二预处理当前状态时i时,有谁和我可以不碰撞,且融合后合理的方案
        for(int i = 0; i < 1 << n; i ++)
        {
            state[i].clear();
            for(int j = 0; j < 1 << n; j ++)
                if(!(i & j) && st[i|j])
                    state[i].push_back(j);
        }

        //正式开始dp
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for(int i = 1; i <= m; i ++)//当前是讨论第i列
            for(int j = 0; j < 1 << n; j ++)//第i列的状态是j
                for(auto x : state[j])//与状态j匹配的状态全部在state[j]里面
                    f[i][j] += f[i-1][x];


        cout << f[m][0] << endl;
    }

    return 0;
}


活动打卡代码 AcWing 286. 选课

kuan525
9天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;
int h[N], e[N], ne[N], idx;
int w[N], f[N][N];
int n, m;

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

void dfs(int u){//把以u节点为根的子树处理完毕
    //枚举当前节点的邻接表
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        dfs(j);

        //开始分组背包
        for(int k = m; k >= 0; k --)//从大到小枚举,这里利用了滚动数字,经典问题
            for(int s = 1; s <= k; s ++)
                f[u][k] = max(f[u][k], f[u][k-s] + f[j][s]);//处理当前所有子树的集合

    }
    //前面处理了当前为根的树的所有子树,现在来处理自己,需要将自己加上去
    for(int i = m; i >= 1; i --)
        f[u][i] = f[u][i-1] + w[u];
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i ++)
    {
        int a, b; cin >> a >> b;
        add(a, i); w[i] = b;
    }
    m ++;

    dfs(0);
    cout << f[0][m] << endl;
    return 0;
}



kuan525
9天前
//没有上司的舞会
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 6010, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], idx;
int happy[N];
bool st[N];
int f[N][2];// 表示以i为根节点,j=0表示选i,j=1表示不选i

void add(int b, int a)//b后面加a*********这里顺序不要搞反了,很难发现
{
    e[idx] = a; ne[idx] = h[b]; h[b] = idx ++;
}

int dfs(int head)//k是一个状态值
{
    f[head][1] = happy[head];

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

        dfs(j);

        f[head][1] += f[j][0];//选自己, 累加,所有儿子的子孙的开心指数也要加起来

        f[head][0] += max(f[j][1], f[j][0]) ;//不选自己

    }

}

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

    memset(h, -1, sizeof h);

    for(int i = 1; i < n; i ++)
    {
        int a, b; cin >> a >> b;//b是a的直接上司
        st[a] = true;
        add(b, a);//b后面加a
    }

    int head;//head为根节点
    for(int i = 1; i <= n; i ++) 
        if(st[i] == false) 
            head = i;

    dfs(head);

    cout << max(f[head][1], f[head][0]) << endl;

    return 0;
}