蓝桥中的四道DP

2022-4-5 16:29:33


1226. 包子凑数 (0pts)

多重背包? 我直接G。

Q1:多重背包的时间复杂度?

我把完全背包和多重背包记错了

f [ i ] f[i] f[i] 表示使用前 i i i 个蒸笼,

4,5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
x x	x	  x x        x                 
a A1 + b A2 + c A3 + ... + n An

1070. 括号配对(一道我很久之前就想做的题)

阶段咋划分?

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

#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;

const int N = 110;

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

bool ck(char a,char b){
    if(a=='['&&b==']'){
        return 1;
    }
    if(a=='('&&b==')'){
        return 1;
    }
    return 0;
}

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

    for(int len=1;len<=n;len++){
        for(int l=1;len+l-1<=n;l++){
            int r = l+len-1;
            if(ck(s[l],s[r])){
                f[l][r] = max(f[l][r],f[l+1][r-1] + 2);
            }
            /*不能写else
            关于转移写else会wa。
			集合划分的不严格,
			考虑,括号序列:[]([]
			ans = f[1][5] = 4 , 但是匹配的话 f[2][4]+2 = 0+2 = 2 ,还需要划分更新最大值,f[1][2]+f[3][5] = 2+2=4
            */
            for(int k=l;k<r;k++){
                f[l][r] = max(f[l][r],f[l][k]+f[k+1][r]);
            }
        }
    }
    cout<< n - f[1][n]<<endl;
    return 0;
}
1078. 旅游规划

第一眼以为是最短路…

用bfs求树的直径,顺带记录每个点之前的点的编号,然后从最远的点,向回递归加入一个set。 4/10

发现自己编号写成了1~n,改了改,不知道为啥只能对俩了。

1217. 垒骰子 (DP+矩阵快速幂优化)

A组省赛的题目还是有点难度的。

样例我都算不出来,我是白痴

一个骰子六个面,确定一个面之后,剩下的四个面可以旋转。

废废的了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int mod = 1e9+7, N = 1e6+10;
int n,m;
set<int>st[10];
ll f[N];//f[i]表示在满足约束限制下,放好了前i个骰子的所有摆放方案。
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        st[a].insert(b);
        st[b].insert(a);
    }
    f[0]=1;
    f[1]=24;
    for(int i=2;i<=n;i++){
        int cnt=0;
        for(int k=1;k<=6;k++){//第i-1层的顶部摆放k
            int x = 6 - st[k].size();
            cnt += x;
        }
        cout<<cnt<<endl;
        f[i] = (f[i] + f[i-1] * cnt * 4)%mod;
        cout<<i<<" "<<f[i]<<endl;
    }
    
    cout<<f[n]<<endl;
    return 0;
}

看懂了别人的DP代码,我可以想到状态定义,也可以想到状态计算,但是我不明白为什么我这么只用一维是不行的。

定义: f [ i ] [ j ] f[i][j] f[i][j] 从下向上已经摆好了 i i i 个骰子,并且最上边的骰子的顶面是 j j j 的所有合法的方案数。

转移的时候枚举第 i i i 层顶面的数字,再枚举第 i − 1 i-1 i1 层顶面的数字就行。

因为 n n n 特别大,能直接想到用滚动数组或者使用矩阵快速幂进行优化。

非常惊讶,这么写滚动数组竟然是错的
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int mod = 1e9+7, N = 1e6+10;
int n,m;
bool op[10][10];
ll f[10][10];//f[i]表示在满足约束限制下,放好了前i个骰子的所有摆放方案。
int ag[10];

void init(){
    ag[1]=4,ag[2]=5,ag[3]=6;
    ag[4]=1,ag[5]=2,ag[6]=3;
}

int main(){
    init();
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        op[a][b]=op[b][a]=true;
    }
    /* 
        for(int i=1;i<=6;i++)f[0][i]=6, 这得多SB才能这么初始化啊
    */
    
    for(int i=1;i<=6;i++)f[1][i]=4;
    
    for(int i=2;i<=n;i++){
        for(int j=1;j<=6;j++){
            for(int k=1;k<=6;k++){
                if(op[ag[j]][k])continue;
                f[i&1][j] = (f[i&1][j] + (ll)4*f[(i-1)&1][k]) % mod;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=6;i++){
        ans = (ans + f[n&1][i])%mod;
    }
    cout<<ans<<endl;
    
    return 0;
}

学到了一个trick。

如果递推式的第 i i i 层只和之前的 i − 1 i-1 i1 层有关,可以直接使用 i & 1 i\&1 i&1 滚动数组优化。

这题,第 i i i 层和第 i i i , i − 1 i-1 i1 层有关,每次更新第 i i i 层的时候,需要将上一层清空。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int mod = 1e9+7, N = 1e6+10;
int n,m;
bool op[10][10];
ll f[10][10];//f[i]表示在满足约束限制下,放好了前i个骰子的所有摆放方案。
int ag[10];

void init(){
    ag[1]=4,ag[2]=5,ag[3]=6;
    ag[4]=1,ag[5]=2,ag[6]=3;
}

int main(){
    init();
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        op[a][b]=op[b][a]=true;
    }
    /* 
        for(int i=1;i<=6;i++)f[0][i]=6, 这得多SB才能这么初始化啊
    */
    
    for(int i=1;i<=6;i++)f[1][i]=4;
    
    for(int i=2;i<=n;i++){
        for(int j=1;j<=6;j++){
            f[i&1][j]=0;
            for(int k=1;k<=6;k++){
                if(op[ag[j]][k])continue;
                f[i&1][j] = (f[i&1][j] + (ll)4*f[(i-1)&1][k]) % mod;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=6;i++){
        ans = (ans + f[n&1][i])%mod;
    }
    cout<<ans<<endl;
    
    return 0;
}

考虑如何用矩阵加速。

f [ i ] [ j ] = 4 / 0   f [ i − 1 ] [ 1 ] + 4 / 0   f [ i − 1 ] [ 2 ] + . . . + 4 / 0   f [ i − 1 ] [ 6 ] f[i][j]= 4/0 \ f[i-1][1] + 4/0 \ f[i-1][2] + ... + 4/0 \ f[i-1][6] f[i][j]=4/0 f[i1][1]+4/0 f[i1][2]+...+4/0 f[i1][6]

f [ i − 1 ] [ j ] = 4 / 0   f [ i − 2 ] [ 1 ] + 4 / 0   f [ i − 2 ] [ 2 ] + . . . + 4 / 0   f [ i − 2 ] [ 6 ] f[i-1][j]= 4/0 \ f[i-2][1] + 4/0 \ f[i-2][2] + ... + 4/0 \ f[i-2][6] f[i1][j]=4/0 f[i2][1]+4/0 f[i2][2]+...+4/0 f[i2][6]

每层之间的限制是一样的。所以先确定矩阵 A A A , 然后矩阵快速幂优化。

继续麻
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;
typedef long long ll;
const int mod = 1e9+7, N = 1e6+10;
int n,m;
bool op[10][10];
ll f[7][7];//f[i]表示在满足约束限制下,放好了前i个骰子的所有摆放方案。
ll A[7][7];
int ag[10];

void init(){
    ag[1]=4,ag[2]=5,ag[3]=6;
    ag[4]=1,ag[5]=2,ag[6]=3;
}
/*
将两个矩阵乘法,用一个实现,
*/
void mul(ll f[][7],ll a[][7],ll b[][7]){
    ll tmp[10][10]={0};
    for(int i=1;i<=6;i++){
        for(int j=1;j<=6;j++){
            for(int k=1;k<=6;k++){
                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) %mod;
            }
        }
    }
    memcpy(f,tmp,sizeof tmp);
}

int main(){
    init();
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        op[a][b]=op[b][a]=true;
    }
    /*
    不能这样写,F数组压成一维,j依然是顶层。
    */
    for(int i=1;i<=6;i++){
        for(int j=1;j<=6;j++){
            if(op[i][j]){
                A[i][j]=0;
            }
            else A[i][j]=1;
        } 
    }
    
    for(int i=1;i<=6;i++)f[0][i]=4;
    int t = n;
    while(t){
        if(t&1){
            mul(f,f,A);
        }
        mul(A,A,A);
        t>>=1;
    }
    // for(int i=2;i<=n;i++){
    //     for(int j=1;j<=6;j++){
    //         f[i&1][j]=0;
    //         for(int k=1;k<=6;k++){
    //             if(op[ag[j]][k])continue;
    //             f[i&1][j] = (f[i&1][j] + (ll)4*f[(i-1)&1][k]) % mod;
    //         }
    //     }
    // }
    ll ans=0;
    for(int i=1;i<=6;i++){
        ans = (ans + f[0][i])%mod;
    }
    cout<<ans<<endl;
    
    return 0;
}

用一个小时的时间获得的收获。

tmp矩阵的维数必须和结果矩阵的维数一致,不然就会wa

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;
typedef long long ll;
const int mod = 1e9+7, N = 1e6+10;
int n,m;
bool op[10][10];
ll f[7][7];//f[i]表示在满足约束限制下,放好了前i个骰子的所有摆放方案。
ll A[7][7];
int ag[10];
void print(ll f[][7]){
    for(int i=1;i<=6;i++){
        for(int j=1;j<=6;j++){
            cout<<f[i][j]<<" ";
        }
        cout<<endl;
    }
}
void init(){
    ag[1]=4,ag[2]=5,ag[3]=6;
    ag[4]=1,ag[5]=2,ag[6]=3;
}
/*
将两个矩阵乘法,用一个实现,
*/
void mul(ll f[][7],ll a[][7],ll b[][7]){
    //ll tmp[10][10]={0};  大woc了! 第二维不一样,直接导致数组偏移了。
    //ll tmp[10][7]={0}; 这样特tm不对!
    ll tmp[7][7]={0}; // 必须和要求的数组完全一样才行
    for(int i=1;i<=6;i++){
        for(int j=1;j<=6;j++){
            for(int k=1;k<=6;k++){
                tmp[i][j] = (tmp[i][j]%mod + (a[i][k] * b[k][j])%mod) %mod;
            }
        }
    }
    memcpy(f,tmp,sizeof tmp);
}

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

    for(int i=1;i<=6;i++)
        for(int j=1;j<=6;j++)
            A[i][j]=4;

    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        A[a][ag[b]]=A[b][ag[a]]=0;
    }

    for(int i=1;i<=6;i++)f[1][i]=4;

    int t = n-1;
    while(t){
        if(t&1){
            mul(f,f,A);
        }
        mul(A,A,A);
        t>>=1;
    }
    ll ans=0;
    for(int i=1;i<=6;i++){
        ans = (ans + f[1][i])%mod;
    }
    cout<<ans<<endl;

    return 0;
}
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值