我不理解
  • 板块P6249 神帖
  • 楼主sipu6174
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/6/16 19:34
  • 上次更新2023/11/7 00:31:42
查看原帖
我不理解
239832
sipu6174楼主2020/6/16 19:34

为什么过不了样例

#include<bits/stdc++.h>
using namespace std;
const int N=210;
long long f[N][N][501][2];//【左端点】【右端点】【时间】【在左 OR 在右】    快乐值 
long long maxt,maxn,sta;
struct node{
	int x,v,t;
}t[N];
bool cmp(node x,node y){
	return x.x<y.x;
}
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i].x>>t[i].v>>t[i].t;
	}n++;t[n]=node{0,0,0};  // 在中间插个原点方便DP 
	sort(t+1,t+1+n,cmp);
	
	for(int i=1;i<=n;i++)
		if(t[i].x==0) sta=i;

	f[sta][sta][0][0]=f[sta][sta][0][1]=0; 
	
	for(int i=sta;i;i--)
	for(int j=sta;j<=n;j++)
	
		if(i!=j){
			int t1=abs(t[i].x-t[i+1].x),
				t2=abs(t[i].x-t[j].x),
				t3=abs(t[i].x-t[j].x),
				t4=abs(t[j-1].x-t[j].x);
			for(int ti=1;ti<=500;ti++){
				int add1=(t[i].t>=ti?t[i].v:0);
				int add2=(t[i].t>=ti?t[i].v:0);
				int add3=(t[j].t>=ti?t[j].v:0);
				int add4=(t[j].t>=ti?t[j].v:0);
				if(ti>=t1) f[i][j][ti][0]=max(f[i][j][ti-1][0],f[i+1][j][ti-t1][0]+add1);
				if(ti>=t2) f[i][j][ti][0]=max(f[i][j][ti-1][0],f[i+1][j][ti-t2][1]+add2);
				if(ti>=t3) f[i][j][ti][1]=max(f[i][j][ti-1][1],f[i][j-1][ti-t3][0]+add3);
				if(ti>=t4) f[i][j][ti][1]=max(f[i][j][ti-1][1],f[i][j-1][ti-t4][1]+add4);
				
				maxn=max(f[i][j][ti][0],f[i][j][ti][1]);
			}	
		}
	cout<<maxn;			
}
2020/6/16 19:34
加载中...