题目描述 从起点到终点有N步，如果“走”第K步，将会得到A[K]元钱，A[K]可能为负数。 你也可以花100元钱“跳过”当前的这一步，即不会得到A[K]。但是任何时刻身上的钱都必须是非负的。开始时，你身上共有0元。给定数组A，求在能到达终点的情况下最小需要走过（即不是用100元钱跳过）的步数。注意：最后一步必须走，不能选择跳过。
输入 共有两行。 第一行为整数N（0<=N<=100）。 第二行有N个整数，第K个数为A[K]，-10000<=A[K]<=10000，。
输出 一个整数，表示需要走的最少步数。若无法走到终点，输出-1。
样例输入 6 30 30 30 30 30 30
样例输出 5
解题思路：我们可以看到，这道题的数据同样非常水 所以，我们可以用一个1ms的DFS（Depth first search 深度优先搜索）来做这道题。很多同学也是用深搜，可是没有过（50分~90分）左右，我们在这里可以再做出剪枝优化。 首先，我们要分两种情况来深搜。n≤100，也就是说最大应该是2^100次方这么多次递归，显然这是超时的。根据题目要求的最优解，我们可以写出第一个剪枝：只要现在的步数≥ans了，那么就返回。 这是完全暴力的方法（60分）
#include<cstdio> #include<cstring> using namespace std; int f[150][105],a[105],n; long long ans=10000000; void putin() { memset(f,3000,sizeof(f)); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); } void dfs(int x,int y,int z) { f[x][z]=y; if(x==n) { if(y+a[x]>=0&&z+1<ans) ans=z+1; return ; } if(y-100>=0) dfs(x+1,y-100,z); if(y+a[x]>=0) dfs(x+1,y+a[x],z+1); } int main() { freopen("steps.in","r",stdin); freopen("steps.out","w",stdout); putin(); dfs(1,0,0); if(ans==10000000) printf("-1"); else printf("%lld",ans); return 0; }这是经过一次剪枝的方法（70分）
#include<cstdio> #include<cstring> using namespace std; int f[150][105],a[105],n; long long ans=10000000; void putin() { memset(f,3000,sizeof(f)); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); } void dfs(int x,int y,int z) { if(z+1>=ans) return ; f[x][z]=y; if(x==n) { if(y+a[x]>=0&&z+1<ans) ans=z+1; return ; } if(y-100>=0) dfs(x+1,y-100,z); if(y+a[x]>=0) dfs(x+1,y+a[x],z+1); } int main() { freopen("steps.in","r",stdin); freopen("steps.out","w",stdout); putin(); dfs(1,0,0); if(ans==10000000) printf("-1"); else printf("%lld",ans); return 0; }这时我们可以考虑如果现在剩下的费用比原来还小，那要不要再继续递归下去了呢？ 这个答案显然是 不是的。 所以我们给出最后一个优化，那就是现在剩下的费用比原来还小就退出。而我们这里就要用到数组F了，F[i][j]表示走到i走了j步的花费。 满分程序（双剪枝搜索，1ms就过了）
#include<cstdio> #include<cstring> using namespace std; int f[150][105],a[105],n; long long ans=10000000; void putin() { memset(f,3000,sizeof(f)); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); } void dfs(int x,int y,int z) { if(z+1>=ans||y<=f[x][z]) return ; f[x][z]=y; if(x==n) { if(y+a[x]>=0&&z+1<ans) ans=z+1; return ; } if(y-100>=0) dfs(x+1,y-100,z); if(y+a[x]>=0) dfs(x+1,y+a[x],z+1); } int main() { freopen("steps.in","r",stdin); freopen("steps.out","w",stdout); putin(); dfs(1,0,0); if(ans==10000000) printf("-1"); else printf("%lld",ans); return 0; }这道题其实还有DP方法，但是我还没有想出来。大家可以自行想一下，如何做到DP解题。 最后谢谢大家的观看，留个赞吧！谢谢！
