萌新求问 dp
查看原帖
萌新求问 dp
398190
lanretE楼主2022/7/1 09:49

rt,这份代码,我认为没问题,但是交上去全 WA,然后我一看测试点,发现输出和答案好像都是两倍关系,于是我脑子一热把 ans 除以二再输出,就过了

请问是为什么,这份代码里面为什么会算到重复呢

#include<iostream>
#include<cmath>
#define ll long long
#define QwQ cout<<"QwQ"<<endl;
using namespace std;
const int N=10010;
int f[N],t[N],x[N],y[N]; 
int main(){
	int n,m,ans=0; cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>t[i]>>x[i]>>y[i];
		f[i]=1;
		for(int j=1;j<=i;++j)
			if(f[j]+1>f[i] && abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]) f[i]=f[j]+1;
		ans=max(ans,f[i]);
	}
	cout<<ans<<endl;
	return 0;
}
2022/7/1 09:49
加载中...