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就错了,难道收益会是负数?