编程竞赛与动态规划：矩阵快速幂优化解题思路-CSDN博客

本文链接：https://blog.csdn.net/hacker__man/article/details/123979285

2022-4-5 16:29:33

1226. 包子凑数（0pts）

多重背包？我直接G。

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

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

$f [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]$ 从下向上已经摆好了 $i$ 个骰子，并且最上边的骰子的顶面是 $j$ 的所有合法的方案数。

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

因为 $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 - 1$ 层有关，可以直接使用 $i\&1$ 滚动数组优化。

这题，第 $i$ 层和第 $i$ , $i - 1$ 层有关，每次更新第 $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-1][1] + 4/0 \ f[i-1][2] + ... + 4/0 \ f[i-1][6]$

$\ f[i-2][1] + 4/0 \ f[i-2][2] + ... + 4/0 \ f[i-2][6]$

每层之间的限制是一样的。所以先确定矩阵 $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;
}