3935773_tle.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 73 行

#include <iostream>
using namespace std;
int fale[100001][101];//费用记录表
int max_height,min1,min2,max_height_number;
int N,C;
int input[101];
int direction;
int fill(int count);
int set(int count,int i,int abjust_height_fale);
int jdz(int a);
int main()
{
	cin>>N;
	cin>>C;
	max_height=0;max_height_number=0;direction=0;
	int count=0;
	for(count=1;count<=N;count++) 
	{
		cin>>input[count];
		if(input[count]>max_height) 
		{
			max_height_number=count;
			max_height=input[count];
		}
	}
	fale[max_height_number][max_height]=0;
	direction=-1;
	for(count=max_height_number-1;count>=1;count--)//负方向搜索
	{
		min1=fill(count);
	}
	direction=1;
	for(count=max_height_number+1;count<=N;count++)//正方向搜索
	{
		min2=fill(count);	
	}
	cout<<min1+min2;
	return 0;
}
int fill(int count)
{
	int i=0;
	int min=0,temp=0;
	int abjust_height_fale=0;
	for(i=input[count];i<=max_height;i++)
	{
		abjust_height_fale=(i-input[count])*(i-input[count]);
		temp=set(count,i,abjust_height_fale);
		if(i=input[count]) min=temp;
		else if(temp<min) min=temp;
	}
	return min;
}
int set(int count,int i,int abjust_height_fale)
{
	int j=0;
	int min=0,temp=0;
	for(j=input[count-direction];j<=max_height;j++)
	{
		temp=abjust_height_fale+jdz(j-i)*C+fale[count-direction][j];
		if(j=input[count-direction]) min=temp;
		else if(temp<min) min=temp;
	}
	fale[count][i]=min;
	return min;
}
int jdz(int a)
{
	if(a>=0) return a;
	else return (0-a);
}