图片说明

这一题是真正的DP，ZT大佬一开始想递归地去解决。这个是正向思维，然后程序就进死循环了。（

可以从小到大递推，先对所有的数对判断是否互质，完成初始化。

然后就是递推的关键：

注意到必须满足从小到大递推的性质，所以要以主对角线为方向铺设。

最后注意因为第一行（列）没有上一行（列），而且1与任何数互质，所以直接设置，预处理也是可以的，我当时要是预处理就没那么多屁事了。

#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
void solve() {
    for (int i = 1; i <= 1000; ++i)
        for (int j = i; j <= 1000; ++j)
            if (__gcd(i, j) == 1)
                dp[i][j] = dp[j][i] = 1;
            else
                dp[i][j] = dp[j][i] = 0;
    for (int x = 1; x <= 1000; ++x)
        for (int y = x; y <= 1000; ++y) {
            dp[x][y] += max(dp[x - 1][y], dp[y - 1][x]);
            dp[y][x] = dp[x][y];
            if (x == 1) dp[x][y] = y;//比赛的时候因为这个的位置往上摆了两行一直想不明白为什么过不了案例
            if (y == 1) dp[x][y] = x;
        }
}
int main() {
    solve();
    int T, a, b;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &a, &b);
        printf("%d\n", dp[a][b]);
    }
    return 0;
}

当然有更简洁的写法

#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main() {
    for (int i = 1; i <= 1000; ++i) dp[1][i] = i;
    for (int i = 2; i <= 1000; ++i)
        for (int j = i; j <= 1000; ++j)
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + (__gcd(i, j) == 1);
    int t, a, b;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &a, &b);
        if (a > b) swap(a, b);
        printf("%d\n", dp[a][b]);
    }
    return 0;
}

两种写法都是670ms