Jimmy规定一个三角形的三条边的长度均为正整数，希望聪明的你帮忙求三边之和不超过n的直角三角形个数。 提示：a、b、c是直角三角形三条边的长度，a、b是两条直角边长度，c是斜边长度，它们满足a²+b²=c²。

可以用两层循环枚举直角边 a 和 b 的长度，然后计算出 c 的长度，如果满足 a²+b²=c² 且 a+b+c≤n，则符合条件，计数器加一。代码如下：

#include <iostream>
using namespace std;

int main() {
    int n, count = 0;
    cin >> n;
    for (int a = 1; a < n; a++) {
        for (int b = a; b < n; b++) {
            int c = sqrt(a * a + b * b);
            if (a * a + b * b == c * c && a + b + c <= n) {
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

该算法的时间复杂度为 O(n^2logn)，其中 n 为直角边最大值。由于开方运算的时间复杂度较高，因此程序执行速度可能较慢。如果希望加快程序的执行速度，可以将开方运算替换为整数平方根函数，例如 GMP 库中的 `mpz_sqrt` 函数。

相关问题

【题目描述】 第二题:三角形问题(triangle) Jimmy 规定一个三角形的三条边的长度均为正整数，希望聪明的你帮忙求三 边之和不超过 n 的直角三角形个数。 提示:a、b、c 是直角三角形三条边的长度，a、b 是两条直角边长度，c 是 斜边长度，它们满足 a2+b2=c2。

好的，让我来回答你的问题。关于三角形问题，我们可以先枚举三条边的长度，然后判断是否满足直角三角形的条件，即$a^2+b^2=c^2$。如果满足条件，则这三条边可以组成一个直角三角形。另外，我们还需要保证三条边的长度之和不超过给定的$n$，如果满足这个条件，则直角三角形的数量加1。最后枚举完所有可能的三条边长度，就可以得到直角三角形的总数。

下面是具体的实现代码，你可以参考一下：

def count_right_triangles(n):
    count = 0
    for a in range(1, n):
        for b in range(a, n):
            c = (a ** 2 + b ** 2) ** 0.5
            if c == int(c) and a + b + c <= n:
                count += 1
    return count

这个函数的参数是$n$，表示三条边之和不超过$n$。函数返回的是直角三角形的数量。你可以调用这个函数来得到三角形问题的答案。

Jimmy 作为一名 SCUT 的大学生，自然需要去学习。 在 SCUT，Jimmy 的课表上有 N 门不同的课程，在学期的每一周内他总共会上 N 次课，每一门课程恰好一周上一次课，Jimmy 对于每一个课程都有一个熟练度，初始时都为 0。 对于一节课 Jimmy 可以选择如下两种选项之一： 1. 去上课：如果 Jimmy 选择去上课，此时他对于这节课的熟练度增加 AiAi​。 2. 翘课：Jimmy 热爱学习，因此他会在翘课的时候找地方自学，此时他对于这节课的熟练度增加 BiBi​。 为了去学习更多的课外知识，Jimmy 不会在其余时间学习这 N 门课程，但是他又不想要让自己的成绩排名靠后，于是他找到了你，请你帮忙让他在每周恰好翘 k 门课时，他所有课程熟练度总和尽可能大。 输入格式 第一行两个整数 N, k 接下来一行 N 个整数 AiAi​。 接下来一行 N 个整数 BiBi​。 输出格式 仅输出一行一个整数，表示 Jimmy 在每周恰好翘 k 门课时所有课程熟练度总和的最大值。用c++实现，时间限制2s，内存限制256MB，N最大值是10000000

根据题目数据范围，我们可以发现 $N$ 可能会很大，因此需要对原来的二维动态规划进行优化。

首先，可以发现 $f[i][j]$ 只与 $f[i-1][j]$ 和 $f[i-1][j-1]$ 有关，因此可以使用滚动数组将空间复杂度优化为 $O(k)$。

其次，对于每一门课程，选择上课和选择翘课，可以分别看作是在原有基础上增加了 $a_i+b_i$ 和 $b_i$ 的贡献，因此可以将 $a_i+b_i$ 和 $b_i$ 分别存储到两个数组中，然后使用差分的思想将问题转化为一个区间翻转的问题。

具体思路如下：

1. 定义 $f[j]$ 表示翘了 $j$ 门课时，所有课程熟练度总和的最大值。

2. 初始化 $f[0] = 0$。

3. 对于每一门课，使用差分思想将 $a_i+b_i$ 和 $b_i$ 的贡献分别存储到两个数组中。

4. 对于每一门课，从 $k$ 到 $1$ 枚举翘课的门数 $j$，更新 $f[j]$：

- 如果 $j$ 恰好等于 $k$，则需要将 $a_i+b_i$ 的贡献加到 $f[j]$ 中。

- 否则，需要将 $b_i$ 的贡献加到 $f[j]$ 中，并且使用差分的思想更新 $f[j]$ 和 $f[j-1]$。

5. 最终答案为 $\max\limits_{i=0}^k f[i]$。

时间复杂度为 $O(nk)$，空间复杂度为 $O(k)$。

下面是用 C++ 实现的代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e7 + 10;

int n, k;
int a[N], b[N];
int f[N];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) cin >> b[i];

    for (int i = 1; i <= n; i ++ ) a[i] += b[i];

    memset(f, 0xcf, sizeof f);
    f[0] = 0;

    for (int i = 1; i <= n; i ++ )
        for (int j = k; j >= 1; j -- )
        {
            if (j == k) f[j] += a[i];
            else
            {
                int t = f[j];
                f[j] = max(f[j], f[j - 1] + b[i]);
                f[j - 1] = max(f[j - 1], t + a[i] - b[i]);
            }
        }

    int res = -1e9;
    for (int i = 0; i <= k; i ++ )
        res = max(res, f[i]);

    cout << res << endl;

    return 0;
}