其实我想问一下，为什么一定要使用区间dp，不能用贪心，比如我下面这种。每次选择相邻两个加和最小的，把他们加起来。能不能举个反例啥的。

#include<bits/stdc++.h>
using namespace std;

const int ZUIDA=200000001;

int n,tiLi=0;

struct dui{
	int x;
	bool valid;
	int pre,nex;
}d[10003];

struct zuHe{
	int l,r;
	int he;
};

struct Compare{
	bool operator()(zuHe a,zuHe b){
		return a.he>b.he;
	}
};

priority_queue<zuHe,vector<zuHe>,Compare> q;

void heBing(dui& w,dui& v){
	w.x+=v.x;
	w.nex=v.nex;
	d[v.nex].pre=v.pre;
	v.valid=false;
}

bool is_valid(zuHe w){
	return w.l!=-1 && w.r!=-1 && d[w.l].valid && d[w.r].valid && d[w.l].x+d[w.r].x==w.he;
}

int main(){
	cin>>n;
	d[0].x=ZUIDA;
	d[0].pre=-1;
	d[0].nex=1;
	d[0].valid=false;
	for (int i=1;i<=n;i++)
	{
		cin>>d[i].x;
		d[i].nex=i+1;
		d[i].pre=i-1;
		d[i].valid=true;
		q.push({i-1,i,d[i-1].x+d[i].x});
	}
	d[n+1].x=ZUIDA;
	d[n+1].pre=n;
	d[n+1].nex=-1;
	d[n+1].valid=false;
	while (!q.empty()){
		while(!q.empty() && !is_valid(q.top())){
			q.pop();//TODO
		}
		if (q.empty()) break;
		zuHe t=q.top();
		tiLi+=t.he;
		heBing(d[t.l],d[t.r]);
		q.push({t.l,d[t.l].nex,d[t.l].x+d[d[t.l].nex].x});
		q.push({d[t.l].pre,t.l,d[t.l].x+d[d[t.l].pre].x});
		q.pop();
	}
	cout<<tiLi;
	return 0;
}