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

題目傳送門

題目描述：

S o l u t i o n Solution Solution

很容易發現一個性質：不管前面選取哪些人，一定會有一個人是剩下的不被選取的，
因此我們設 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]表示當前狀態中選的兩個里的第一個和第二個，以及上一個狀態下剩下的那一個

遞回轉移即可，

C o d e Code 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);
}