您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

ZZULIOJ 2825: 收集金币

2825: 收集金币icon-default.png?t=M3K6http://acm.zzuli.edu.cn/problem.php?id=2825可以用一个二维数组

f[i][0]表示没有使用过技能;

f[i][1]表示使用过技能;

我们可以找出这个题的状态转移方程:

f[i][0]=f[i][0]+x;

f[i][1]=max(f[i][0],f[i][1]+x);

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL f[20010][2];
int main()
{
	int t;cin>>t;
	while(t--)
	{
		int n;cin>>n;
		memset(f,0,sizeof f);
		f[0][0]=0;
		f[0][1]=-1e11;
		for(int i=1;i<=n;i++)
		{
			string s;int x;
			cin>>s>>x;
			if(s=="LOST")
			{
				f[i][0]=max(f[i-1][0]-x,0ll);
				f[i][1]=max(f[i-1][0],max(f[i-1][1]-x,0ll));
			}
			else
			{
				f[i][0]=f[i-1][0]+x;
				f[i][1]=f[i-1][1]+x;
			}
		}
		cout<<max(f[n][0],f[n][1])<<endl;
	}
	return 0;
	
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进