有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），要求：计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。

这是一个经典的动态规划问题。我们可以通过定义一个数组dp[i]来表示使用总重量不超过i的砝码能称出的不同重量的个数。初始状态dp[0]=1，表示没有使用任何砝码时，能称出的重量个数为1（即重量为0）。

接着，我们按照砝码的重量顺序，对于每个砝码，更新dp数组。对于每个砝码重量j（1g、2g、3g、5g、10g、20g），我们需要更新所有dp[i]（i >= j），使其等于不使用该砝码时的重量个数加上使用该砝码时的重量个数。具体来说，对于每个j，我们遍历所有i >= j，将dp[i]更新为dp[i] + dp[i - j]。

这样，当遍历完所有砝码后，dp[1000]中就记录了使用总重量不超过1000g的砝码能称出的不同重量的个数。

具体算法步骤如下：
1. 初始化dp数组，dp[0]=1，其余为0。
2. 按照砝码重量1g、2g、3g、5g、10g、20g的顺序，对于每个砝码重量j，遍历dp数组从j到1000，更新dp[i]为dp[i] + dp[i - j]。
3. 最终dp[1000]即为所求的不同重量的个数。

下面是一个简单的示例代码（伪代码），用于演示上述动态规划的思路：

初始化 dp[0...1000] 为0
dp[0] = 1
砝码数组 weights = [1, 2, 3, 5, 10, 20]

对于每个砝码重量 w in weights:
    对于 i 从 w 到 1000:
        dp[i] = dp[i] + dp[i - w]

返回 dp[1000]

相关问题

对E11 (1,6)上的点G=(2,7)，计算2G，3G，4G，5G的值。

给定E11上的椭圆曲线方程为：$y^2=x^3+x+6$，点G=(2,7)。

首先计算2G的值：

计算斜率$k=\frac{3x^2+1}{2y}=\frac{3\cdot2^2+1}{2\cdot7}=\frac{13}{14}$。

然后根据加法公式计算2G的值：

$x_2=k^2-x_1-x_1= \left(\frac{13}{14}\right)^2-2-2=-\frac{489}{196}$

$y_2=k(x_1-x_2)-y_1=\frac{13}{14}(2+\frac{489}{196})-7=\frac{345}{196}$

因为$(x_2,y_2)$不在E11上，需要将其变换到E11上。计算$x_2^{-1}\bmod{11}$的值为$5$，则

$x_2=5(-\frac{489}{196})=4$

$2G=(4,6)$。

接下来，我们可以用类似的方法计算3G、4G和5G的值：

- 3G=2G+G
- $k=\frac{y_2-y_1}{x_2-x_1}=\frac{3}{4}$
- $x_3=k^2-x_1-x_2=\frac{25}{16}-4-4=-\frac{39}{16}$
- $y_3=k(x_1-x_3)-y_1=\frac{3}{4}(4+\frac{39}{16})-6=\frac{63}{16}$
- $3G=(-\frac{39}{16}, \frac{63}{16})$
- 4G=2(2G)
- $k=\frac{y_2-y_1}{x_2-x_1}=\frac{5}{9}$
- $x_4=k^2-x_2-x_2=\frac{25}{81}-4-4=-\frac{332}{81}$
- $y_4=k(x_2-x_4)-y_2=\frac{5}{9}(4+\frac{332}{81})-\frac{345}{196}=\frac{935}{81}$
- $4G=(-\frac{332}{81}, \frac{935}{81})$
- 5G=4G+G
- $k=\frac{y_4-y_1}{x_4-x_1}=\frac{11}{9}$
- $x_5=k^2-x_1-x_4=\frac{121}{81}-4+\frac{332}{81}=\frac{373}{81}$
- $y_5=k(x_1-x_5)-y_1=\frac{11}{9}(2-\frac{373}{81})-7=-\frac{34883}{6561}$
- $5G=(\frac{373}{81}, -\frac{34883}{6561})$

因此，2G=(4,6)，3G=(-39/16,63/16)，4G=(-332/81,935/81)，5G=(373/81,-34883/6561)。

请用c++实现以下题目有一片矩形的阵地，有a行b列。现在在第x行、第y列埋上了炸弹，如果从埋上炸弹的地方开始走（可以向上、向下、向左、向右4个方向走）n步之内（包括0步）都会被炸到，请问有多少点会被炸到。 输入格式: 共1行，为a，b，x，y，n。 输出格式: 共1行，问有多少点会被炸到。 限制: 10%的数据满足： 1<=x<=a<=100 1<=y<=b<=100 1<=n<=10 30%的数据满足： 1<=x<=a<=1000 1<=y<=b<=1000 1<=n<=100 100%的数据满足：1<=x<=a<=2.1*10^9 1<=y<=b<=2.1*10^9 1<=n<=10000 样例 1 : 输入: 6 7 3 2 4 输出: 27

以下是C++实现的代码，使用了BFS算法：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 2005;

int a, b, x, y, n;
bool g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int bfs()
{
    queue<pair<int, int>> q;
    q.push({x, y});
    g[x][y] = true;

    int res = 1;
    while (n--)
    {
        int len = q.size();
        while (len--)
        {
            auto t = q.front();
            q.pop();

            for (int i = 0; i < 4; i++)
            {
                int nx = t.first + dx[i], ny = t.second + dy[i];
                if (nx >= 1 && nx <= a && ny >= 1 && ny <= b && !g[nx][ny])
                {
                    g[nx][ny] = true;
                    q.push({nx, ny});
                    res++;
                }
            }
        }
    }

    return res;
}

int main()
{
    cin >> a >> b >> x >> y >> n;
    cout << bfs() << endl;
    return 0;
}