CCPC-Wannafly Winter Camp Day1 (Div2)

目录

B 吃豆豆（dp）

C 拆拆拆数

F 爬爬爬山

J 夺宝奇兵

B 吃豆豆（dp）

【分析】dp。三维数组dp[i][j][k]表示位置(i,j)在第k秒最多可以获得的糖果数。通过k-1秒的5种状态转移到第k秒；

             dp[i][j-1][k-1]，dp[i][j+1][k-1]，dp[i-1][j][k-1]，dp[i+1][j][k-1]，dp[i][j][[k-1]

             初始化dp数组时要赋值负无穷，赋值-1会wa，暂时还没想清楚为什么...

【代码】

//3维DP维护一个3维数组，表示(i,j)位置第K秒有多少糖果，
//通过k-1秒5个位置转移得到(i,j,k)
#include<cstring>
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
const int maxn=1e4+5;int dp[15][15][maxn];//位置（i，j）在第k秒有多少糖果 
int T[15][15];
int n,m,c;
int xs,ys,xt,yt;int main()
{scanf("%d%d%d",&n,&m,&c);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&T[i][j]);scanf("%d%d%d%d",&xs,&ys,&xt,&yt);memset(dp,-0x3f3f3f3f,sizeof(dp));dp[xs][ys][0]=0;for(int k=1;k<maxn;k++)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dp[i][j][k]=max(dp[i-1][j][k-1],//upmax(dp[i][j+1][k-1],//rightmax(dp[i+1][j][k-1],//dowmmax(dp[i][j-1][k-1],//leftdp[i][j][k-1]//no move))))+(k%T[i][j]==0?1:0);int maxx=-1;for(int i=0;i<maxn;i++)if(dp[xt][yt][i]>=c){maxx=i;break;}printf("%d\n",maxx);
}

C 拆拆拆数

【分析】其实就两种情况

1. 如果A和B本身就互质，那么就是A和B本身，一组；
2. 如果A和B不互质，那么总能把A和B各拆成2个数使得两两互质，这样是2组；

暴力枚举就好，但是枚举的上限当然不能是A和B了，数据范围太大肯定会T的。

在一个博主那看到说是枚举到100就可以了，说是因为AB分类分别减2或3或5或7就可以拆成两组互质的数了

贴一个构造正解https://www.cnblogs.com/Dup4/p/10296448.html

【代码】

#include<cstring>
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;int main()
{int t;scanf("%d",&t);while(t--){ll A,B,flag=0;scanf("%lld%lld",&A,&B);if(__gcd(A,B)==1)printf("1\n%lld %lld\n",A,B);else{for(ll i=2;i<200;i++){for(ll j=2;j<200;j++){if(__gcd(i,j)==1 && __gcd(A-i,B-j)==1){printf("2\n%lld %lld\n%lld %lld\n",i,j,A-i,B-j);flag=1;break;}}if(flag)break;}}}
}

F 爬爬爬山

【分析】wls最大能爬上的高度是maxH=h[1]+k；因为上升耗体力，但是下降又得体力。所以把大于maxH的山降低即可；

【代码】堆优化的dijkstra，我...还不会写，先留坑

J 夺宝奇兵

待补..