给定一个序列，每次从前三个中选两个值并取他们的最大值累加，不足 3 个就取剩下的 1 个或 2 个的最大值累加，
求和的最小值以及取法。
每一次会取两个数，也就是会剩下一个数，所以我们可以把剩下的那个数来设状态
F[ i] [j ] 前i个数，剩余的数为j
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int N =1003;
struct T{
int k,i,j;
}p[N][N];
int n,f[N][N],a[N];
void print(int x,int y){
if(x>1) print(x-1,p[x][y].k);
if(p[x][y].i>n){printf("%d\n", p[x][y].j);return;}
if(p[x][y].j>n){printf("%d\n", p[x][y].i);return;}
printf("%d %d\n",p[x][y].i,p[x][y].j);
}
void solve(){
int i,j;
memset(f,127,sizeof f);
cin>>n;for(i=1;i<=n;i++) cin>>a[i]; n++;
f[0][1]=0;
for(i=1;i<=n/2;i++)
for(j=1;j<i*2;j++){
if(f[i][j]>f[i-1][j]+max(a[i*2],a[i*2+1]))
f[i][j]=f[i-1][j]+max(a[i*2],a[i*2+1]),
p[i][j]=T{j,i*2,i*2+1};
if(f[i][2*i]>f[i-1][j]+max(a[i*2+1],a[j]))
f[i][2*i]=f[i-1][j]+max(a[i*2+1],a[j]),
p[i][2*i]=T{j,i*2+1,j};
if(f[i][2*i+1]>f[i-1][j]+max(a[i*2],a[j]))
f[i][2*i+1]=f[i-1][j]+max(a[i*2],a[j]),
p[i][2*i+1]=T{j,i*2,j};
}
cout<<f[n/2][n]<<endl; print(n/2,n);
}
signed main(){
solve();
}