住房和城乡建设部网站进不去,搭建网站服务器多少钱,营销型网站建设实训报告个人总结,如何建立公司网站电话发现更多计算机知识#xff0c;欢迎访问Cr不是铬的个人网站
D迷宫逃脱 拿到题目一眼应该就能看出是可以用动态规划来解决。但是怎么定义dp呢?
这个题增加难度的点就在当所在位置与下一个要去的位置互质的时候#xff0c;会消耗一把钥匙。当没有钥匙的时候就不能移动了。想…发现更多计算机知识欢迎访问Cr不是铬的个人网站
D迷宫逃脱 拿到题目一眼应该就能看出是可以用动态规划来解决。但是怎么定义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 4e057;
const LL N1e0510;
const LL mod1e097;
typedef pairint,intpl;
priority_queueLL , vectorLL, greaterLL t;
priority_queueLL 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;//读入行宽与高还要钥匙数目cinnmp;//适当开大一点//dp[i][j][k]表示从(1,1)到(i,j)消耗k把钥匙的最大路径和LL dp[n5][m5][p5];LL a[n5][m5];for(int i 1; i n;i)for(int j 1; j m;j)cina[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(maxx0)coutmaxxendl;elsecout-1endl;return 0;
}
E深秋的苹果 这个是一道二分的题目中规中矩写就行但是注意此题右端点要开很大!
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 4e057;
const LL N2e0510;
const LL mod1e097;
typedef pairint,intpl;
priority_queueLL , vectorLL, greaterLL t;
priority_queueLL 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);cinnm;for(int i 0; i n;i)cina[i];//二分思路LL l 0, r 3e18;//开大点,防止意外while( l r){LL mid l (r - l)/ 2; //避免可能的超界if(check(mid)) { r mid; }else { l mid 1; }}coutlendl;return 0;
} 本文由博客一文多发平台 OpenWrite 发布
