小蒟蒻的疑惑
查看原帖
小蒟蒻的疑惑
324573
Sin_qwq楼主2021/10/20 16:37

WA码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
const int N=10100;
struct node{
	int val,date;
//	bool operator < (const node &x)const{return date<x.date;}
}a[N];
bool cmp(node x,node y)
{
	if(x.date!=y.date) return x.date<y.date;
	return x.val>y.val;
}
int n,ans=-1;
int f[N];
int read()
{
	char ch=getchar();int x=0,cf=1;
	while(ch<'0'||ch>'9'){if(ch=='-') cf=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*cf;
}
signed main()
{
	while(cin>>n)
	{
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)
		{
			a[i].val=read();
			a[i].date=read();
		}
		sort(a+1,a+n+1,cmp);
//        sort(a+1,a+n+1);
        ans=-1;//此处不同
		for(int i=1;i<=n;i++)
		{
			for(int j=a[i].date;j;j--)
			{
				f[j]=max(f[j],f[j-1]+a[i].val);
				ans=max(f[j],ans);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

AC码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
const int N=10100;
struct node{
	int val,date;
//	bool operator < (const node &x)const{return date<x.date;}
}a[N];
bool cmp(node x,node y)
{
	if(x.date!=y.date) return x.date<y.date;
	return x.val>y.val;
}
int n,ans=-1;
int f[N];
int read()
{
	char ch=getchar();int x=0,cf=1;
	while(ch<'0'||ch>'9'){if(ch=='-') cf=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*cf;
}
signed main()
{
	while(cin>>n)
	{
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)
		{
			a[i].val=read();
			a[i].date=read();
		}
		sort(a+1,a+n+1,cmp);
//        sort(a+1,a+n+1);
        ans=0;//此处不同
		for(int i=1;i<=n;i++)
		{
			for(int j=a[i].date;j;j--)
			{
				f[j]=max(f[j],f[j-1]+a[i].val);
				ans=max(f[j],ans);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

为啥ans要初始化为0而-1就错了,难道收益会是负数?

2021/10/20 16:37
加载中...