给定一个序列\(a_i\)，每次可以删除前\(3\)个中的\(2\)个，代价为所删两数的\(a_i\)最大值；若数字个数小于\(3\)，就一次删完，代价同样为\(a_i\)最大值。求删掉所有数的最小代价以及方案。

\(n\le 1000,1\le a_i\le 10^6\)

Solution

这样的删数方式很特别，我们需要寻找一些性质。

从序列的形状上看，没有被删的数应该是 一个单点+一个后缀，也可能只有一个后缀。

啥，你说咋看出来的？后缀显然，单点多删几次就可以发现。

那不就很好dp了吗。

设\(f_{i,j}\)表示单点位置为\(i\)，后缀左端点为\(j\)时，最小代价是多少。

刷表，讨论删掉前\(3\)个中的哪\(2\)个。

\(f_{i,j}\)可以贡献到：

• \(f_{i,j+2}\)
• \(f_{j+1,j+1}\)
• \(f_{j,j+2}\)

还要考虑只有后缀的情况，不妨设当\(i=j\)时，后缀为从\(i\)开始的区间。
\(f_{i,i}\)可以贡献到

• \(f_{i+2,i+2}\)
• \(f_{i+1,i+3}\)
• \(f_{i,i+3}\)

然后就是记录方案。

代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
inline int read(){
	int x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
typedef pair<int,int> pii;
const int N=1005;
int n,a[N],f[N][N],pre[N][N][2];
void upd(int x,int y,int i,int j,int val){
	//用f[i,j]更新f[x,y]，val为转移时的代价 
	if(f[x][y]>f[i][j]+val){
		f[x][y]=f[i][j]+val;
		pre[x][y][0]=i;
		pre[x][y][1]=j;
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	memset(f,0x3f,sizeof(f));
	f[1][1]=0;
	for(int i=1;i<=n+2;++i){
		upd(i+2,i+2,i,i,max(a[i],a[i+1]));
		upd(i+1,i+3,i,i,max(a[i],a[i+2]));
		upd(i,i+3,i,i,max(a[i+1],a[i+2]));
		for(int j=i+1;j<=n+2;++j){
			upd(i,j+2,i,j,max(a[j],a[j+1]));
			upd(j+1,j+1,i,j,max(a[i],a[j]));
			upd(j,j+2,i,j,max(a[i],a[j+1])); 
		}
	}
	vector<pii>ans;
	int x,y;
	if(n&1) printf("%d\n",f[n+2][n+2]),x=y=n+2;
	else printf("%d\n",f[n+1][n+1]),x=y=n+1;
	while(x>1||y>1){
		int px=pre[x][y][0],py=pre[x][y][1];
		if(px==py){
			if(x==px+2&&y==py+2) ans.pb(mp(px,px+1));
			if(x==px+1&&y==py+3) ans.pb(mp(px,px+2));
			if(x==px&&y==py+3) ans.pb(mp(px+1,px+2));
		}else{
			if(x==py+1&&y==py+1) ans.pb(mp(px,py));
			if(x==py&&y==py+2) ans.pb(mp(px,py+1));
			if(x==px&&y==py+2) ans.pb(mp(py,py+1));
		}
		x=px;
		y=py;
	}
	reverse(ans.begin(),ans.end());
	for(int i=0;i<ans.size();++i){
//		printf("%d %d\n",ans[i].fi,ans[i].se);
		if(ans[i].fi<=n) printf("%d ",ans[i].fi);
		if(ans[i].se<=n) printf("%d ",ans[i].se);
		printf("\n");
	}
	return 0;
}
/*
给定一个序列，每次可以删除前3个中的2个，代价为max(ai)，剩余一个时代价为a，求最小代价 

剩下的元素是一个单点 & 一个后缀

f[i,j]：单点在i，后缀左端点为j，最小时间为多少

f[i,i] -> f[i+2,i+2],f[i+1,i+3],f[i,i+3]
f[i,j] -> f[i,j+2],f[j+1,j+1],f[j,j+2]
*/