Bestcoder-889-1003-Dec

题目链接

题意：

给定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