求助玄学问题
  • 板块学术版
  • 楼主bzzltl
  • 当前回复9
  • 已保存回复9
  • 发布时间2023/7/26 10:33
  • 上次更新2023/11/3 07:36:54
查看原帖
求助玄学问题
699852
bzzltl楼主2023/7/26 10:33

关于P2569 [SCOI2010] 股票交易这道题,对于 f 数组的初始化操作如下,其中第一个样例输出7,第二个是可以 AC 的代码,两份代码只有赋初值的方式有区别,第一份代码我以为是赋值 IM 导致的溢出,但是开成 long long 后依然没有什么用,求大佬讲解。

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=2e3+6;
const int IM=2147483647;
const long long LLM=9223372036854775807;

inline int read()
{
	int x=0,y=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') y=-y;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^'0');c=getchar();}
	return x*y;
}

int n,m,w,f[2001][2002];
int ap,bp,as,bs;

deque<int>q;
signed main()
{
	n=read(),m=read(),w=read();
	for(int i=1;i<=n;i++)
	{
		ap=read(),bp=read(),as=read(),bs=read();
		for(int j=1;j<=m;j++) j<=as?f[i][j]=-j*ap:f[i][j]=-IM+10;//
		for(int j=0;j<=m;j++) f[i][j]=max(f[i][j],f[i-1][j]);
		if(i<=w) continue;
		while(q.size()) q.pop_back();
		for(int j=0;j<=m;j++)
		{
			while(q.size()&&q.front()<j-as) q.pop_front();
			while(q.size()&&f[i-w-1][q.back()]+q.back()*ap<=f[i-w-1][j]+j*ap) q.pop_back();
			q.push_back(j);
			f[i][j]=max(f[i][j],f[i-w-1][q.front()]+q.front()*ap-j*ap);
		}
		while(q.size()) q.pop_back();
		for(int j=m;j>=0;j--)
		{
			while(q.size()&&q.front()>j+bs) q.pop_front();
			while(q.size()&&f[i-w-1][q.back()]+q.back()*bp<=f[i-w-1][j]+j*bp) q.pop_back();
			q.push_back(j);
			f[i][j]=max(f[i][j],f[i-w-1][q.front()]+q.front()*bp-j*bp);
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++) ans=max(ans,f[n][i]);
	printf("%lld\n",ans);
	return 0;
}
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=2e3+6;
const int IM=2147483647;
const long long LLM=9223372036854775807;

inline int read()
{
	int x=0,y=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') y=-y;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^'0');c=getchar();}
	return x*y;
}

int n,m,w,f[2001][2002];
int ap,bp,as,bs;

deque<int>q;
signed main()
{
	n=read(),m=read(),w=read();
	memset(f,128,sizeof f);//
	for(int i=1;i<=n;i++)
	{
		ap=read(),bp=read(),as=read(),bs=read();
		for(int j=1;j<=as;j++) f[i][j]=-j*ap;
		for(int j=0;j<=m;j++) f[i][j]=max(f[i][j],f[i-1][j]);
		if(i<=w) continue;
		while(q.size()) q.pop_back();
		for(int j=0;j<=m;j++)
		{
			while(q.size()&&q.front()<j-as) q.pop_front();
			while(q.size()&&f[i-w-1][q.back()]+q.back()*ap<=f[i-w-1][j]+j*ap) q.pop_back();
			q.push_back(j);
			f[i][j]=max(f[i][j],f[i-w-1][q.front()]+q.front()*ap-j*ap);
		}
		while(q.size()) q.pop_back();
		for(int j=m;j>=0;j--)
		{
			while(q.size()&&q.front()>j+bs) q.pop_front();
			while(q.size()&&f[i-w-1][q.back()]+q.back()*bp<=f[i-w-1][j]+j*bp) q.pop_back();
			q.push_back(j);
			f[i][j]=max(f[i][j],f[i-w-1][q.front()]+q.front()*bp-j*bp);
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++) ans=max(ans,f[n][i]);
	printf("%d\n",ans);
	return 0;
}
2023/7/26 10:33
加载中...