题意
有一列数，每次从前三个中选两个（不足两个则选一个）其中较大者为代价，接着这两个数出列，求让所有数出列的最小代价。
题解
状态不好设
讲的人都这么说
第(i)轮选数后，总共会选(2×i)个数，所以在第(i)轮选数时，是在（前(i-1)轮选数后剩下的那一个数（第(j)个数）和第(i*2)个数，第(i*2+1)个数）这三个数中选两个，剩一个。
所以设(f_i,_j)为第(i)轮，剩下第(j)个数时的最小代价
有三种状态转移（剩第(j)个数(要枚举的)、剩第(2*i)个数、剩第(（2*i+1）)个数）
式子：
[f_{i,j}=min(f_{i,j}, f_{i-1,j}+max(a_{2*i},a_{2*i+1}))
]
[f_{i,2*i}=min(f_{i,2*i}, f_{i-1,j}+max(a_{j},a_{2*i+1}))
]
[f_{i,2*i+1}=min(f_{i,2*i+1}, f_{i-1,j}+max(a_{j},a_{2*i}))
]
但是还要方案，再来一个结构体(path)记录
(p[i][j].i)和(p[i][j].j)记录第(i)层剩第(j)个时选的那两个数，(p[i][j].k)记录上一层剩的是哪个数，以便递归输出。
注意事项
一、初始化(f)为INF，(f_{0,1}=0)
二、(n)++
这里是为了保证最后一轮时不剩下不该剩下的(1)~(n)
保证最后一轮剩下的是原来的(n)+(1)。
Code
#include<bits/stdc++.h>
using namespace std;
struct path{int k,i,j;}p[1010][1010];
int n,ans=1e9,final,a[1010],f[1010][1010];
inline int read(){
int w=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w;
}
inline void output(int px, int py){
if(px>1) output(px-1,p[px][py].k);
if(p[px][py].i>n){printf("%d
", p[px][py].j);return;}
if(p[px][py].j>n){printf("%d
", p[px][py].i);return;}
printf("%d %d
",p[px][py].i,p[px][py].j);
return;
}
int main(){
n=read();
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++) a[i]=read();
n++;
f[0][1]=0;
for(int i=1;i<=n/2;i++){
for(int j=1;j<(i<<1);j++){
if(f[i-1][j]+max(a[i<<1],a[i<<1|1])<f[i][j]){
f[i][j]=f[i-1][j]+max(a[i<<1],a[i<<1|1]);
p[i][j]=(path){j,i<<1,i<<1|1};
}
if(f[i-1][j]+max(a[j],a[i<<1])<f[i][i<<1|1]){
f[i][i<<1|1]=f[i-1][j]+max(a[j],a[i<<1]);
p[i][i<<1|1]=(path){j,i<<1,j};
}
if(f[i-1][j]+max(a[j],a[i<<1|1])<f[i][i<<1]){
f[i][i<<1]=f[i-1][j]+max(a[j],a[i<<1|1]);
p[i][i<<1]=(path){j,i<<1|1,j};
}
}
}
printf("%d
",f[n/2][n]);
output(n/2,n);
return 0;
}