最小步数

小楠正在玩一个游戏，规则为：

从起点到终点有 n 步，如果走第 k 步，小楠将会得到 a[k] 元钱，a[k] 可能为负数。小楠也可以花 100 元钱跳过当前的这一步，即不会得到 a[k] 。但是任何时刻身上的钱都必须是非负的。

开始时，小楠身上共有 0 元。给定数组 a ，求在能到达终点的情况下最少需要走过（即不是用100 元钱跳过）的步数。

90pts priority_queue

#include
using namespace std;
#define int long long
int n,a[1010],ans,money;
bool flag=1;
priority_queue<int>q;
signed main()
{
	freopen("steps.in","r",stdin);
	freopen("steps.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
	{
		if(a[i]+100<=0)
		{
			money-=100;
			if(money>=100) ans+=1;
			else
			{
				ans++;
				while(money<0)
				{
					if(q.empty()) break;
					money+=100+q.top();
					q.pop();
					ans--;
				}
				if(money<0)
				{
					puts("-1");
					flag=0;break;
				}
			}
		}
		else
		{
			if(a[i]<0)
			{
				if(money>=100)
				{
					money-=100;
					q.push(a[i]);
					ans++;
				}
				else
				{
					money+=a[i];
					if(money<0)
					{
						while(money<0)
						{
							if(q.empty()) break;
							money+=100+q.top();
							q.pop();
							ans--;
						}
						if(money<0)
						{
							puts("-1");
							flag=0;break;
						}
					}
				}
			}
			else
			{
				if(money>=100)
				{
					money-=100;
					q.push(a[i]);
					ans++;
				}
				else money+=a[i];
			}
		}
	}
	if(flag) printf("%lld",n-ans);
	return 0;
}

AC DP：
注意17 19 22 行，其中17 19要考虑到有可能结果money为正，但是过程money为负，所以有第一个条件，22行是要注意for(int j=1;j

#include
using namespace std;
#define int long long
int n,a[1010],f[210][210];
signed main()
{
	freopen("steps.in","r",stdin);
	freopen("steps.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	memset(f,-0x3f3f3f3f,sizeof f);
	for(int i=0;i<=n;i++) f[0][i]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j
		{
			if(f[i-1][j-1]>=0&&f[i-1][j-1]+a[i]>=0)
				f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);
			if(f[i-1][j]>=100&&f[i-1][j]>=0)
				f[i][j]=max(f[i][j],f[i-1][j]-100);
		}
		if(f[i-1][i-1]+a[i]>=0&&f[i-1][i-1]>=0)
			f[i][i]=f[i-1][i-1]+a[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(f[n][i]>=0)
		{
			printf("%lld\n",i);
			return 0;
		}
	}
	puts("-1");
	return 0;
}