这里提供两部分代码：

1. 标准题解代码：使用二进制拆分优化多重背包的 $O(NM \cdot \log K \cdot \min(TI, A))$ 解法。
2. 数据生成器：用于生成 1-10 测试点的输入输出文件，覆盖了从小数据到满数据、特殊边界（如体力不足、全是0等）的情况。

1. 标准题解代码 (C++) (有错误，有一半WA）

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义背包中的物品结构
struct Item {
    int cost;  // 代价 (时间和体力消耗相同)
    int value; // 桃子数量
};

int main() {
    // 优化IO
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M, TI, A;
    if (!(cin >> N >> M >> TI >> A)) return 0;

    // 实际限制是时间与体力的较小值
    int limit = min(TI, A);

    // 读取桃子数量矩阵
    vector<vector<int>> peach(N + 1, vector<int>(M + 1));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> peach[i][j];
        }
    }

    // 读取可采摘次数矩阵并进行二进制拆分构建物品列表
    vector<Item> items;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            int k;
            cin >> k;
            
            // 如果该位置没桃子或者次数为0，跳过
            if (peach[i][j] == 0 || k == 0) continue;

            // 计算单次往返的代价：(行坐标+列坐标) * 2
            // 题目定义左上角是(1,1)，Life在(0,0)，距离是 i+j
            int single_cost = (i + j) * 2;

            // 如果单次代价都已经超过限制，这棵树无法到达，直接跳过
            if (single_cost > limit) continue;

            int single_value = peach[i][j];

            // 二进制拆分：将 k 次拆分为 1, 2, 4, ... 
            // 转化为 0/1 背包问题
            int count = 1;
            while (k >= count) {
                items.push_back({single_cost * count, single_value * count});
                k -= count;
                count *= 2;
            }
            if (k > 0) {
                items.push_back({single_cost * k, single_value * k});
            }
        }
    }

    // 0/1 背包 DP
    // dp[v] 表示消耗 v 的代价能获得的最大桃子数
    vector<long long> dp(limit + 1, 0);

    for (const auto& item : items) {
        for (int v = limit; v >= item.cost; v--) {
            dp[v] = max(dp[v], dp[v - item.cost] + item.value);
        }
    }

    cout << dp[limit] << endl;

    return 0;
}

2. 数据生成器 (Data Generator)

这个程序会在当前目录下生成 1.in/1.out 到 10.in/10.out。

测试点设计策略：

• Test 1-2: 极小数据 (N, M <= 5)，手动验证容易。
• Test 3-4: 中等数据 (N, M <= 20)，验证逻辑正确性。
• Test 5: 边界 - 体力/时间极少，几乎哪里都去不了。
• Test 6: 边界 - 桃子很多但 K=0 (有些树不能摘)。
• Test 7: 边界 - 某些树特别远，远超限制 (测试剪枝)。
• Test 8: 较大 K 值，测试二进制拆分效率。
• Test 9: 满数据 (N, M = 100)，测试最大规模。
• Test 10: 随机大数据，所有数值打满。

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <random>
#include <chrono>

using namespace std;

// ================== 核心解法 (用于生成 .out) ==================
long long solve_case(int N, int M, int TI, int A, 
                     const vector<vector<int>>& P, 
                     const vector<vector<int>>& K_mat) {
    int limit = min(TI, A);
    struct Item { int cost; int value; };
    vector<Item> items;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            int p_val = P[i-1][j-1];
            int k_cnt = K_mat[i-1][j-1];

            if (p_val == 0 || k_cnt == 0) continue;

            int single_cost = (i + j) * 2;
            if (single_cost > limit) continue;

            int count = 1;
            while (k_cnt >= count) {
                items.push_back({single_cost * count, p_val * count});
                k_cnt -= count;
                count *= 2;
            }
            if (k_cnt > 0) {
                items.push_back({single_cost * k_cnt, p_val * k_cnt});
            }
        }
    }

    vector<long long> dp(limit + 1, 0);
    for (const auto& item : items) {
        for (int v = limit; v >= item.cost; v--) {
            dp[v] = max(dp[v], dp[v - item.cost] + item.value);
        }
    }
    return dp[limit];
}

// ================== 数据生成工具 ==================

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

void generate_case(int case_id, int n, int m, int max_ti, int max_a, int max_p, int max_k, string type = "random") {
    string in_file = to_string(case_id) + ".in";
    string out_file = to_string(case_id) + ".out";

    ofstream fout(in_file);

    // 生成参数
    int ti = random_int(max(1, max_ti / 2), max_ti);
    int a = random_int(max(1, max_a / 2), max_a);
    
    // 特殊类型覆盖
    if (type == "impossible") { // 哪都去不了
        ti = 1; a = 1;
    } else if (type == "infinite_stamina") {
        a = 10000; ti = max_ti;
    } else if (type == "infinite_time") {
        ti = 10000; a = max_a;
    }

    fout << n << " " << m << " " << ti << " " << a << endl;

    vector<vector<int>> peach(n, vector<int>(m));
    vector<vector<int>> k_mat(n, vector<int>(m));

    // 生成桃子矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (type == "sparse") { // 稀疏矩阵，大部分是0
                peach[i][j] = (random_int(0, 10) > 8) ? random_int(1, max_p) : 0;
            } else {
                peach[i][j] = random_int(0, max_p);
            }
            fout << peach[i][j] << (j == m - 1 ? "" : " ");
        }
        fout << endl;
    }

    // 生成次数矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (type == "zero_k") { // 有桃子但这棵树不能摘
                k_mat[i][j] = 0;
            } else {
                k_mat[i][j] = random_int(0, max_k);
            }
            fout << k_mat[i][j] << (j == m - 1 ? "" : " ");
        }
        fout << endl;
    }
    fout.close();

    // 计算答案
    long long ans = solve_case(n, m, ti, a, peach, k_mat);
    ofstream f_ans(out_file);
    f_ans << ans << endl;
    f_ans.close();

    cout << "Generated Case " << case_id << ": N=" << n << " M=" << m << " -> Ans=" << ans << endl;
}

int main() {
    // 题目约束猜测: 10% -> 100, 30% -> 50. 假设满分为100%数据 N,M <= 100.
    // 时间和体力如果不限制可能会很大，但在题目中通常配合 N,M 限制。
    // 为了DP可解，Limit 不会过大，假设 Limit <= 1000 左右较为合理。

    // 1. 极小数据
    generate_case(1, 4, 4, 15, 15, 10, 2);
    
    // 2. 小数据
    generate_case(2, 5, 5, 20, 30, 20, 5);

    // 3. 边界: 哪都去不了 (Time/Stamina = 1)
    generate_case(3, 10, 10, 100, 100, 50, 10, "impossible");

    // 4. 边界: 有桃子但 K=0
    generate_case(4, 10, 10, 50, 50, 50, 10, "zero_k");

    // 5. 中等数据，稀疏桃子
    generate_case(5, 20, 20, 100, 100, 100, 20, "sparse");

    // 6. 中等数据，体力无限，受时间限制
    generate_case(6, 30, 30, 150, 150, 50, 50, "infinite_stamina");

    // 7. 中等数据，时间无限，受体力限制
    generate_case(7, 30, 30, 150, 150, 50, 50, "infinite_time");

    // 8. 较大 K 值 (K=100)
    generate_case(8, 40, 40, 200, 200, 20, 100);

    // 9. 满数据 N=50 (接近 30% 数据范围的上限，或者通常 OJ 的中高档)
    // 题目描述有点模糊，这里假设 100 是上限
    generate_case(9, 80, 80, 500, 500, 100, 80);

    // 10. 最大数据 N=100, TI=500
    generate_case(10, 100, 100, 600, 600, 200, 100);

    cout << "All test cases generated successfully!" << endl;
    return 0;
}

你好！我是你的OI教练。很高兴能带你分析这道《科技庄园》。

这道题表面上看着像是一个“迷宫搜索”或者“图论”题，因为有坐标、有移动。但如果你仔细分析它的代价计算方式，你会发现它其实是一个披着地图外衣的背包问题。

咱们不动代码，先用草稿纸把模型剥离出来。

第一部分：思路提示

1. 识破“双重限制”的障眼法 题目里有两个限制：时间 $TI$ 和 体力 $A$。

• 每移动一格，消耗 1 秒时间，同时消耗 1 点体力。
• 摘桃子不花时间也不花体力。
• 思考：既然消耗的速率是一模一样的（都是走一步耗一点），那其实这两个限制是“穿一条裤子”的。
• 结论：你实际能消耗的总额度，就是 $\min(TI, A)$。比如你有 100 秒时间但只有 50 体力，那你最多只能走 50 步，多了就累趴下了。

2. 计算“单次代价” 题目说“每次摘完后都要返回出发点”。这意味着你不能在树林里转圈圈摘，必须是 (0,0) -> 树 -> (0,0) 这样的折返跑。

• 假设一棵桃树在 $(r, c)$。
• 去程距离（曼哈顿距离）：$|r-0| + |c-0| = r + c$。
• 单次总代价（往返）：$2 \times (r + c)$。
• 如果 $2 \times (r + c)$ 大于你的总额度，这棵树你就别想了，太远了。

3. 模型的转化 现在的局面是：

• 你有一个背包，容量是 $W = \min(TI, A)$。
• 地图上有很多种“物品”（桃树）。
• 对于位置 $(i, j)$ 的桃树：
  • 它重（代价）：$2 \times (i + j)$。
  • 它价值（桃数）：$T_{i,j}$。
  • 它数量（限摘）：$K_{i,j}$ 次。
• 结论：这就是标准的多重背包问题（Bounded Knapsack Problem）！

第二部分：预备知识点总结

要解决这道题，你需要掌握：

1. 曼哈顿距离：在只能上下左右移动的网格中，两点距离公式。
2. 动态规划 - 多重背包：
   • 定义：一种物品有限制的数量，求最大价值。
   • 朴素解法：把它看成 $K$ 个一样的物品，直接用 0/1 背包做（三层循环）。
   • 二进制拆分优化（进阶）：如果 $K$ 很大，朴素解法会超时。通过把 $K$ 拆成 $1, 2, 4, \dots$ 的组合，可以将复杂度降低到 $O(W \cdot \sum \log K)$。
     • 注：看题目数据范围，如果 $N,M,TI$ 比较小，可能朴素解法能过；但作为教练建议掌握二进制拆分，这是通法。
3. 一维数组滚动优化：背包问题通常只需要一维数组 dp[v] 来节省空间。

第三部分：启发式教学 —— 草稿纸上的推理

来，拿起笔，我们把这道题从“地图”变成“清单”，再变成“表格”。

步骤一：提取有效容量

假设输入：

TI = 13 (时间)
A  = 20 (体力)

教练提问：你最多能用多少代价？

• 草稿纸写：$Limit = \min(13, 20) = 13$。

步骤二：地图“压扁”成物品单

假设地图上有两个点有桃子（忽略其他的 0）：

1. 位置 $(1, 1)$: 桃子 10 个，能摘 1 次。
2. 位置 $(2, 3)$: 桃子 10 个，能摘 2 次。

请在草稿纸上计算它们的“价格”：

• 物品 A (来自 1,1):

  • 单程距离：$1 + 1 = 2$
  • 花费（往返）：$2 \times 2 = 4$
  • 价值：10
  • 数量：1

• 物品 B (来自 2,3):

  • 单程距离：$2 + 3 = 5$
  • 花费（往返）：$5 \times 2 = 10$
  • 价值：10
  • 数量：2

步骤三：二进制拆分（优化演示）

如果有个物品 C，花费 2，价值 5，数量 $K=13$。 我们要把它拆成几个“打包好的大物品”，以免循环 13 次。

• $13 = 1 + 2 + 4 + 6$
• 我们在物品清单里加入 4 个新物品：
  1. 花费 $1\times2$, 价值 $1\times5$
  2. 花费 $2\times2$, 价值 $2\times5$
  3. 花费 $4\times2$, 价值 $4\times5$
  4. 花费 $6\times2$, 价值 $6\times5$ 这样我们做 0/1 背包时，只需要处理 4 个物品，而不是 13 个。

步骤四：推导 DP 表格

回到步骤二的数据。容量 $Limit = 13$。 物品清单：

1. 物品 A: 花费 4, 价值 10
2. 物品 B1 (拆分): 花费 10, 价值 10 (这是把 B 的第1次摘取看作物品)
3. 物品 B2 (拆分): 花费 10, 价值 10 (这是把 B 的第2次摘取看作物品)

我们定义 dp[v] 为：花费 $v$ 的代价能得到的最大桃子数。 初始化 dp 全为 0。

第一轮：考虑物品 A (费4, 价值10)

• 从 $v=13$ 倒推到 $4$:
  • dp[13] = max(dp[13], dp[13-4] + 10) -> 10
  • ...
  • dp[4] = 10

第二轮：考虑物品 B1 (费10, 价值10)

• 从 $v=13$ 倒推到 $10$:
  • dp[13] 原本是 10。现在看 dp[13-10] + 10 即 dp[3] + 10。
  • dp[3] 是 0，所以结果是 10。没变化（因为只能选 A 或者 B1，选 A 剩 9，不够买 B1；选 B1 剩 3，不够买 A）。
  • 但是，等等！样例说明里说结果是 10。
  • 让我们看看样例的情况：
    • (1,1) 花费 4。
    • (2,3) 花费 10。
    • 总容量 13。
    • 确实只能二选一。要么摘 A 剩 9，要么摘 B 剩 3。
    • 如果你有 14 的容量，你就可以 dp[14] = dp[14-10] + 10。dp[4] 是 10，所以 10+10=20。

教练总结：

1. 读入 $N, M, TI, A$，算出背包容量。
2. 双重循环遍历地图 $(i, j)$。
3. 如果该点有桃子，算出花费 $Cost = 2(i+j)$。
4. 根据该点的次数 $K$，进行二进制拆分，把它们变成一个个独立的“0/1 背包物品”，存入一个大的 vector 或者数组里。
   • 物品属性：{cost, value}
5. 最后跑一遍标准的 0/1 背包模板。
6. 输出 dp[容量]。

思路清晰了吗？去把这个“摘桃子”的背包填满吧！

旧版题解 不用管

C++ :

#include<iostream>
using namespace std;
int i,j,k,l,n,m,v,u,g,tim;
int f[11000],s[1100][1100],q[1100][1100];
int w[1110000],c[1100000];
int num=1,ans;
int main()
{
    //乍一看，有一个想法，这不是一个二维背包咩？ 
    //但这题有个很好的BUG，其实也不算了，就是一个很好玩的条件
    //PET童鞋每秒移动一个单位，每移动一个单位耗一点体力 
    //这就成了01了！ 
    //对了，还有，注意PET童鞋比较那啥，他的路程是要跑两次的！ 
    int t;
    cin>>n>>m>>tim>>t;//矩阵长 宽 时间 体力 
    f[0]=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>s[i][j];
        }//能摘的桃数量 
    } 
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
    {
    cin>>q[i][j];//能摘的次数 
        if(s[i][j]>0)//如果这棵树能摘 
        {
            for(int v=num;v<=num+q[i][j];v++)
            //有一点提醒一下，就是上面那句for循环，注意num的值！ 
            //num是可摘总数 （物品数量！） 
            {
                w[v]=(i+j)*2;//w[]是花费（可以这么说），就是物体体积了啦！
                c[v]=s[i][j]; //提一下，c[]为价值，就不说了哈！ 
            }
        }num+=q[i][j];//桃纸的总数 
    }
    }
    t=min(t-1,tim);//不多解释 ，前面有讲（应该讲了，没讲提醒一下）； 
    for(i=1;i<=num;i++)
    for(j=t;j>=w[i];j--)
    {
        if(j-w[i]<0) break;//这一部分不解释 
        else
        f[j]=max(f[j],f[j-w[i]]+c[i]);//状态转移大方程，不多解释（要解释的童鞋~吱~一声） 
    }
    cout<<f[t]<<endl;
}

Pascal :

program skyline;
var
  w,c,t:array[1..10000]of longint;
  f:array[0..100]of longint;
  num:array[1..100,1..100]of longint;
  n,m,ti,a,i,j,k,tot,time:longint;
begin
{  assign(input,'manor.in');reset(input);
 assign(output,'manor.out');rewrite(output);}
  readln(n,m,ti,a);
  dec(a);
  if ti<a then a:=ti;
  for i:=1 to n do
   for j:=1 to m do
   read(num[i,j]);
  for i:=1 to n do
   for j:=1 to m do
   begin
   read(time);
   if (num[i,j]>0)and(time>0) then begin
      inc(tot);
      w[tot]:=(i+j)*2;
      c[tot]:=num[i,j];
      t[tot]:=time;
      end;
   end;
  for i:=1 to tot do
   for j:=a downto w[i] do
    for k:=1 to t[i] do
   if (j>=w[i]*k)and(f[j-w[i]*k]+c[i]*k>f[j]) then f[j]:=f[j-w[i]*k]+c[i]*k;
  writeln(f[a]);
  {close(input);close(output);}
end.