蓝桥杯 第 3 场算法双周赛4，7题

迷宫逃脱

一眼数字三角形模型，因为是要求最大值，而且对转移状态有限制，所以需要注意dp状态的初始化，可以将所有状态赋值为-0x7f，然后将dp[0][1]和dp[1][0]初始化为0，又因为考虑到起始点a[1][1]，若其价值为1的话，我们就会消耗掉一个钥匙，因为gcd(0,1）=1，所以dp[1][1][1]这个点初始化为a[1][1]的值即可。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"ll dp[1005][1005][5];ll a[1005][1005];void solve()
{int n,m,q;cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) cin>>a[i][j];}memset(dp,-0x3f,sizeof dp);for(int i=1;i<=q+1;i++){dp[0][1][i]=dp[1][0][i]=0;}dp[1][1][1]=a[1][1];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=1;k<=q+1;k++){if(i==1&&j==1) continue;ll x=a[i][j-1],y=a[i-1][j];if(__gcd(x,a[i][j])==1){dp[i][j][k]=max(dp[i][j-1][k-1]+a[i][j],dp[i][j][k]);}else dp[i][j][k]=max(dp[i][j-1][k]+a[i][j],dp[i][j][k]);if(__gcd(y,a[i][j])==1) dp[i][j][k]=max(dp[i-1][j][k-1]+a[i][j],dp[i][j][k]);else dp[i][j][k]=max(dp[i-1][j][k]+a[i][j],dp[i][j][k]);}}}ll ans=-1;// for(int i=1;i<=n;i++){//     for(int j=1;j<=m;j++) cout<<dp[i][j][2]<<" ";//     cout<<endl;// }for(int i=1;i<=q+1;i++) ans=max(ans,dp[n][m][i]);cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}// system("pause");return 0;
}

斐波拉契跳跃

思路：sg+记忆化搜索。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
#define endl "\n"int fi[N];
int len,n;
int f[N][405];
int a[N];
int sg(int x,int id)
{if(f[x][id]!=-1) return f[x][id];set<int> s;for(int i=1;i<=len;i++){if(i<=id) continue;if(x+fi[i]<=n&&a[x+fi[i]]>a[x]) s.insert(sg(x+fi[i],i));if(x-fi[i]>=1&&a[x-fi[i]]>a[x]) s.insert(sg(x-fi[i],i));}for(int i=0;;i++){if(!s.count(i)) return f[x][id]=i;}
}void solve()
{cin>>n;fi[1]=1,fi[2]=2;for(int i=3;;i++){fi[i]=fi[i-1]+fi[i-2];if(fi[i]>n){len=i-1;break;}}memset(f,-1,sizeof f);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){int x=i;if(sg(x,0)!=0) cout<<"Little Lan"<<endl;else cout<<"Little Qiao"<<endl;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}// system("pause");return 0;
}