蓝桥杯第三周算法竞赛D题E题

发现更多计算机知识，欢迎访问Cr不是铬的个人网站

D迷宫逃脱

file 拿到题目一眼应该就能看出是可以用动态规划来解决。但是怎么定义dp呢?

这个题增加难度的点就在当所在位置与下一个要去的位置互质的时候，会消耗一把钥匙。当没有钥匙的时候就不能移动了。想到这里，我们可以定义一个三维的dp数组.

定义dp

dp[i][j][k]表示从位置(1,1)到(i,j)消耗k把钥匙的最大值

初始化

memset(dp,-0x3f3f,sizeof(dp))

dp[i][j][0] = a[1][1]

状态转移方程

dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][k] + a[i][j])

dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][k-1] + a[i][j])互质

dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k] + a[i][j])

dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1] + a[i][j])互质

输出答案

从dp[n][m][0] ~ dp[n][m][k]找到最大的即可

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){
    return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
    return a / gcd(a , b) * b;
}
int main()
{
    //不加不能AC
    //优化输入/输出操作的性能，并精确控制输出的格式
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int n,m,p;
    //读入行宽与高还要钥匙数目
    cin>>n>>m>>p;
    //适当开大一点
    //dp[i][j][k]表示从(1,1)到(i,j)消耗k把钥匙的最大路径和
    LL dp[n+5][m+5][p+5];
    LL a[n+5][m+5];
    for(int i = 1; i <= n;i++)
        for(int j = 1; j <= m;j++)
            cin>>a[i][j];
    //初始化
    memset(dp,-0x3f3f,sizeof(dp));
    dp[1][1][0] = a[1][1];
    for(int i = 1;  i<= n; i++)
        for(int j = 1; j <= m;j++)
            for(int k = 0; k <= p; k++)
            {
                //能够从上转移
                if(i > 1)
                {
                    if(gcd(a[i-1][j],a[i][j]) == 1) {
                        if (k > 0)//不可能出现互质且没消耗一把钥匙的情况
                        { dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1] + a[i][j]); }
                    }
                    else { dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k] + a[i][j]); }
                }
                //能够从左边转移
                if(j > 1)
                {
                    if(gcd(a[i][j-1],a[i][j]) == 1) {
                        if (k > 0)//不可能出现互质且没消耗一把钥匙的情况
                        { dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + a[i][j]); }
                    }
                    else { dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k] + a[i][j]); }
                }
            }
    //适当小一点
    LL maxx = -1e18;
    for(int i = 0; i <= p; i++)
        maxx = max(maxx,dp[n][m][i]);
    if(maxx>0)
        cout<<maxx<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

E深秋的苹果

file 这个是一道二分的题目，中规中矩写就行，但是注意此题右端点要开很大!

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=2e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){
    return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
    return a / gcd(a , b) * b;
}
int n,m;
int a[N];
bool check (LL mid)
{
    LL pre = 0, sum = 0,group = 1;//刚开始就是一组
    for(int i = 0;  i < n;i++)
    {
        if(pre + sum * a[i] <= mid)//可以分在一组
        {
            pre += sum*a[i];
            sum += a[i];
        }
        else//新开一组
        {
            group++;
            pre = 0;
            sum = a[i];//这组开始就是a[i]
        }
        if(group > m)return false;
    }
    return true;
}
int main() {

    //优化输入/输出操作的性能，并精确控制输出的格式
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    cin>>n>>m;
    for(int i = 0; i < n;i++)
        cin>>a[i];
    //二分思路
    LL l = 0, r = 3e18;//开大点,防止意外
    while( l < r)
    {
        LL mid = l + (r - l)/ 2; //避免可能的超界
        if(check(mid)) { r = mid; }
        else { l = mid + 1; }
    }
    cout<<l<<endl;

    return 0;
}