很容易發現一個性質:不管前面選取哪些人,一定會有一個人是剩下的不被選取的。
因此我們設
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示第
i
i
i次選取之後,剩下
j
j
j時的最少能量。
由於一次只能選擇兩個人,而每次前面只剩下一個人,所以選擇第
i
i
i個人時,前三個人只能是
(
i
∗
2
)
(i*2)
(i∗2),
(
i
∗
2
+
1
)
(i*2+1)
(i∗2+1),
(
j
)
(j)
(j),自己手玩很容易證明。
因此我們就可以進行轉移:
因為一次選
2
2
2個人,所以最多選擇
⌈
n
/
2
⌉
\lceil n/2\rceil
⌈n/2⌉次,而這樣選完之後剩下
n
+
1
n+1
n+1號人。
所以最後答案:
f
[
⌈
n
/
2
⌉
]
[
n
+
1
]
f[\lceil n/2\rceil][n+1]
f[⌈n/2⌉][n+1]
至於方案,用一個陣列記錄轉移方案即可
p
r
[
i
]
[
j
]
[
0
/
1
/
2
]
pr[i][j][0/1/2]
pr[i][j][0/1/2]表示當前狀態中選的兩個裡的第一個和第二個,以及上一個狀態下剩下的那一個
遞迴轉移即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3;
int n;
int a[N];
int f[N][N] , pr[N][N][3];
void Print(int x,int y){
if (y == 0) return;
Print(x-1,pr[x][y][2]);
if (pr[x][y][0] <= n) printf("%d ",pr[x][y][0]);
if (pr[x][y][1] <= n) printf("%d ",pr[x][y][1]);
printf("\n");
}
int main(){
scanf("%d",&n);
for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
memset(f,20,sizeof f);
f[1][1] = max(a[2],a[3]);
f[1][2] = max(a[1],a[3]);
f[1][3] = max(a[1],a[2]);
pr[1][1][0] = 2 , pr[1][1][1] = 3 , pr[1][1][2] = 0;
pr[1][2][0] = 1 , pr[1][2][1] = 3 , pr[1][2][2] = 0;
pr[1][3][0] = 1 , pr[1][3][1] = 2 , pr[1][3][2] = 0;
int m = n+1>>1;
for (int i = 2; i <= m; i++){
int x = 2*i , y = 2*i+1;
for (int j = 1; j < x; j++){
if (f[i][j] > f[i-1][j] + max(a[x],a[y])){
f[i][j] = f[i-1][j] + max(a[x],a[y]);
pr[i][j][0] = x , pr[i][j][1] = y , pr[i][j][2] = j;
}
if (f[i][x] > f[i-1][j] + max(a[j],a[y])){
f[i][x] = f[i-1][j] + max(a[j],a[y]);
pr[i][x][0] = j , pr[i][x][1] = y , pr[i][x][2] = j;
}
if (f[i][y] > f[i-1][j] + max(a[j],a[x])){
f[i][y] = f[i-1][j] + max(a[x],a[j]);
pr[i][y][0] = x , pr[i][y][1] = j , pr[i][y][2] = j;
}
}
}
printf("%d\n",f[m][n+1]);
Print(m,n+1);
}