NOIP2005普及T3 采药

Question

NOIP2005普及T3 采药

#include<bits/stdc++.h>
using namespace std;
struct data{
    int time,val;
}a[101];
int T,m,ma,h[102],hi[102];
bool cmp(data x,data y) {
    return x.val*1.0/x.time > y.val*1.0/y.time;
}
inline void dfs(int t,int v,int id){
    if(id>m)return;
    if(t+h[id]<=ma)return;
    if(t+hi[id]>T){
        if(v>ma)ma=v;
        return;
    }
    dfs(t+a[id].time,v+a[id].val,id+1);
    dfs(t,v,id);
}
int main(){
    scanf("%d%d",&T,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&a[i].time,&a[i].val);
    sort(a+1,a+m+1,cmp);
    hi[m+1]=1e9;
    for(int i=m;i>=1;i--){
        h[i]=h[i+1]+a[i].val;
        hi[i]=min(hi[i+1],a[i].time);
    }
    dfs(0,0,1);
    printf("%d",ma);
}

解释一下我的代码为什么会RE，如果你有时间的话告诉我DP版本怎么写。

Answer 1

让【宝码香车】来帮您解答，本回答参考DeepSeek编写，并整理提供。

如果答案让您满意，请采纳、点赞、关注，非常感谢！
.  
每日一句正能量，让它带给您好心情：内心的晴朗，能驱散所有阴霾。
.  

你的代码出现RE（运行时错误）可能有以下几个原因：

1. 数组越界访问：h和hi数组大小是102，但m可能超过100（题目未说明数据范围）
2. 递归深度过大：当m较大时（比如100），递归深度会很大导致栈溢出
3. 边界条件处理不当：比如id超出范围时没有正确处理

DP解法（0/1背包问题标准解法）

#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int T, m;
    cin >> T >> m;
    
    int time[105], val[105];
    for(int i = 1; i <= m; i++) {
        cin >> time[i] >> val[i];
    }
    
    int dp[1005] = {0}; // dp[j]表示时间为j时的最大价值
    
    for(int i = 1; i <= m; i++) {
        for(int j = T; j >= time[i]; j--) {
            dp[j] = max(dp[j], dp[j - time[i]] + val[i]);
        }
    }
    
    cout << dp[T] << endl;
    return 0;
}

原代码问题修正建议

1. 增加数组大小（如改为1005）
2. 添加递归终止条件：if(id > m) return;
3. 考虑使用迭代加深或剪枝优化

DP解法说明

1. 使用经典的0/1背包模型
2. dp[j]表示在时间限制为j时能获得的最大价值
3. 内层循环倒序更新，确保每个物品只被选择一次
4. 时间复杂度O(T*m)，空间复杂度O(T)

DP解法更高效且不会出现栈溢出问题，推荐使用这种方法解决背包类问题。