【題解 && dp】CF82D Two out of Three

題目傳送門

題目描述：

---

$Solution$

很容易發現一個性質：不管前面選取哪些人，一定會有一個人是剩下的不被選取的。
因此我們設$f[i][j]$表示第$i$次選取之後，剩下$j$時的最少能量。
由於一次只能選擇兩個人，而每次前面只剩下一個人，所以選擇第$i$個人時，前三個人只能是$（i\ast 2）$,$(i\ast 2+1)$,$(j)$，自己手玩很容易證明。

因此我們就可以進行轉移：

因為一次選$2$個人，所以最多選擇$\lceil n/2\rceil$次,而這樣選完之後剩下$n+1$號人。
所以最後答案：$f[\lceil n/2\rceil ][n+1]$
至於方案，用一個陣列記錄轉移方案即可
$pr[i][j][0/1/2]$表示當前狀態中選的兩個裡的第一個和第二個，以及上一個狀態下剩下的那一個

遞迴轉移即可。

---

$Code$

#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);
}