关于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;
}