91pts WA on #3 真的看不出哪里错了
查看原帖
91pts WA on #3 真的看不出哪里错了
121813
老子是北瓜楼主2021/7/9 14:10

有大佬指点么?

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 105
#define dbg cout<<"ok";
int m,n,f[1005][N],ff[N];

// f[高度]=饥饿 

struct garbage{
	int t,p,h;
} a[N];

bool cmp(garbage l,garbage r)
{
	return l.t<r.t;
}

int main(){
	cin>>m>>n;
	for(int i=1; i<=n; ++i)
	{
		cin>>a[i].t>>a[i].p>>a[i].h;
	}

	sort(a+1,a+1+n,cmp);
	f[0][0]=11;
	for(int i=1; i<=10; ++i)
		f[i][0]=f[i-1][0]-1;
	for(int i=1; i<=n; ++i)
	{
		int time=a[i].t,food=a[i].p,height=a[i].h;
		//放 
		for(int j=m; j>=height; --j)
			ff[j]=max(f[time][j],f[time][j-height]);
		//吃 
		for(int j=0; j<=m; ++j)
			if(f[time][j]!=0)
				f[time][j]+=food;
		//求最大
		for(int j=0; j<=m; ++j)
			f[time][j]=max(f[time][j],ff[j]); 
		//往后更新 
		for(int j=a[i].t+1; j<=1000; ++j)
			for(int k=0; k<=m; ++k)
				f[j][k]=max(f[j][k],f[j-1][k]-1);
	}
	
	int ans=0;
	for(int i=1; i<=1000; ++i)
		if(f[i][m]!=0){
			ans=i;
			break;
		}
	if(ans!=0)
		cout<<ans;
	else{
		for(int i=1; i<=1000; ++i)
		{
			if(f[i][0]==0){
				ans=i-1;
				break;
			}
		}
		if(ans==0)
			ans=1000+f[1000][0]-1;
		cout<<ans;
	}
	return 0;
}
2021/7/9 14:10
加载中...