记录编号	251735	评测结果	AAAAAAAAAA
题目名称	2240.[HZOI 2016]架设电话线路	最终得分	100
用户昵称	gls1196	是否通过	通过
代码语言	C++	运行时间	0.073 s
提交时间	2016-04-18 15:41:10	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<climits>
#include<cstring>
#include<stack>
#include<cstdlib>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=100;
int f[3][maxn];
int n,c,h;
int Qread(){
	char ch;
	int x=0,ju=1;
	while(ch=getchar(),!isdigit(ch)&&ch!='-');
	if(ch=='-')ju=-1;
	else x=ch-48;
	while(ch=getchar(),isdigit(ch))x=10*x+ch-48;
	return x*ju;
}
int Qabs(int x){
	if(x>0) return x;
	else return -x;
}
int DP(){
	memset(f,0,sizeof(f));
	//原始转移方程：
	//有n*h个状态，每个状态都是有(n-le)或(n-h)哥决策 
	//通过mi加减c的方法提高效率 
	scanf("%d%d%d",&n,&c,&h);
	int la=1,no=0,le=h,k=h;
	for(int j=1;j+h<=100;j++)f[no][j+h]=j*j;//compare
	for(int i=1;i<n;i++){
		h=Qread();
		swap(la,no);//滚动数组 
		k=h;
		int j,mi;
		//注意每次循环的终止位置：< 末边界都在下一次处理 
		if(h<le){
			mi=INT_MAX; 
			//h<le 则对于每一个h，最优的都是由la数组的le~maxn的最优得来的 
			for(j=le;j<=maxn;j++)
				if(mi>f[la][j]+Qabs(j-h)*c)
					mi=f[la][j]+Qabs(j-h)*c;
			for(j=h;j<le;j++){
				f[no][j]=mi;
				mi-=c;
			}
			h=le;//现将no的h~le-1处理到最优 
		}
			
		mi=f[la][le]+Qabs(le-h)*c; 
		//not mi=INT_MAX;
		for(j=le;j<h;j++){
			if(mi>f[la][j]+Qabs(j-h)*c)mi=f[la][j]+Qabs(j-h)*c;
		}
		for(;j<=maxn;j++){
			if(mi>f[la][j])mi=f[la][j];
			f[no][j]=mi;
			mi+=c;
		}
		mi=f[la][maxn]+c;	
		//mi的初始化非常特殊 
		//not mi=INT_MAX;因为更新f[no][maxn-1]会用到  f[no][maxn]只有一种“决策” ，第二次不用更新 
		for(j=maxn-1;j>=h;j--){
			//注意以下判断顺序 
			if(f[la][j]<mi)mi=f[la][j];
			if(f[no][j]>mi)f[no][j]=mi;
			mi+=c;
		}
		for (j=1;j+k<=100;j++) f[no][j+k]+=j*j;
		le=k;
	}
	int ans=INT_MAX;
	for(int i=k;i<=maxn;i++)
		if(ans>f[no][i])
		ans=f[no][i];
	return ans; 
}
int main(){
	freopen("phonewire.in","r",stdin);
	freopen("phonewire.out","w",stdout);
	printf("%d",DP());
	return 0;
}