给定a(1e3),b(1e3)两个正整数,每回合选取一个大于1的数减1,直至两个数均变为1
求过程中两个数互质的最少回合数,多组数据(1e6)
这题看似是个策略题,1e6的数据量把策略的复杂度限制到常数级别,极其困难
于是想到改在线查询为离线查询,预处理好所有可能的结果并存储备用,研究一下复杂度为1e6,可行
于是选择dp,从最终终止条件a=b=1开始逆向转移,每种状态均可由a或b减1转移来,若互质即结果加1
/*
Author Owen_Q
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
int dp[maxn][maxn];
int main()
{
memset(dp,0,sizeof dp);
for(int i=1;i<=1000;i++)
{
for(int j=1;j<=1000;j++)
{
if(i>1)
dp[i][j] = max(dp[i][j],dp[i-1][j]);
if(j>1)
dp[i][j] = max(dp[i][j],dp[i][j-1]);
if(__gcd(i,j)==1)
dp[i][j]++;
}
}
int t;
//freopen(".txt","r",stdin);
//ios::sync_with_stdio(false);
//cin.tie(0);
scanf("%d",&t);
while(t--)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",dp[a][b]);
}
return 0;
}
本文地址:https://blog.csdn.net/Owen_Q/article/details/107503273
如对本文有疑问, 点击进行留言回复!!
Springboot项目因为kackson版本问题启动报错解决方案
Java多线程下的其他组件之CyclicBarrier、Callable、Future和FutureTask详解
网友评论