啊!我连第一个点都过不去,为什么啊!
查看原帖
啊!我连第一个点都过不去,为什么啊!
286752
h1910819075楼主2021/6/17 22:09

求助,大佬们~我看了一个小时了,就是没有发现那里错了,我那里错了呢?我的数组初始化了啊,最开始的数也清空了啊,为什么错了,错那里了?

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+100;
double sum[N],dp[N][N][3];
struct node{
	int x;
	double s,up;
}w[N];

inline int cmp(node s1,node s2)
{
	return s1.x<s2.x;
}

int main()
{
	int n,v,p;
	while(cin>>n>>v>>p)
	{
		if(n==0 )
			break;
			
		for(int i=0;i<=n+1;i++)
			for(int j=0;j<=n+1;j++)
				dp[i][j][1]=dp[i][j][0]=1.0*(0x3f3f3f3f);
				
		int f=0;
		for(int i=1;i<=n;i++)
		{
			cin>>w[i].x>>w[i].s>>w[i].up;
			if(w[i].x==p)
				f=1;
		}
		if(f==0)
		{
			n++;
			w[n].x=p,w[n].s=0,w[n].up=0;	
		}
		sort(w+1,w+1+n,cmp);
		
		double res=0;
		for(int i=1;i<=n;i++)
		{//printf("i=%d %d \n",i,w[i].x);
			if(w[i].x==p)
				dp[i][i][1]=dp[i][i][0]=0;
			sum[i]=sum[i-1]+w[i].up;
			res+=w[i].s;
		}
		
		for(int len=2;len<=n;len++)
		{
			for(int i=1;i+len-1<=n;i++)
			{
				int j=i+len-1;
				dp[i][j][0]=min((dp[i+1][j][0]+(w[i+1].x-w[i].x)*(sum[i]+sum[n]-sum[j])),(dp[i+1][j][1]+(w[j].x-w[i].x)*(sum[i]+sum[n]-sum[j])));
				dp[i][j][1]=min((dp[i][j-1][0]+(w[j].x-w[i].x)*(sum[i-1]+sum[n]-sum[j-1])),(dp[i][j-1][1]+(w[j].x-w[j-1].x)*(sum[i-1]+sum[n]-sum[j-1])));
			}
		}
		
		printf("%.0lf\n",res+min(dp[1][n][1],dp[1][n][0]));
	}
	return 0;
}
2021/6/17 22:09
加载中...