CF 82 D.Two out of Three

前言

全网唯一不同题解

设 \(f[i][j]\) 表示第 \(i\) 次选取留下来的数是 \(k\) 的最小花费

枚举前面的留下来的点 \(k\) 当前能留下的点只有 \((2*i),(2*i+1),k\) 中的一个，时间复杂度 \(O(n^2)\)

选取次数是 \(n/2\) 向上取整。因为最后什么点也不留下，\(a[n+1]=0\)，所以答案可以为 \(f[m][n+1](m=n/2向上取整)\)

另外我没有写记录路径，记录一下也挺简单

Code

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define INF 0x3f3f3f3f

using namespace std;

inline int read() {

	int x=0,f=1; char ch=getchar();

	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }

	while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }

	return x * f;

}

const int N = 1007;

int n;

int a[N];

int f[N][N];

inline int Const(int x,int y) {

	return max(a[x], a[y]);

}

int main()

{

	n = read();

	for(int i=1;i<=n;++i)

		a[i] = read();

	memset(f, 0x3f, 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]);

	int m = n&1 ? n/2+1 : n/2;

	for(int i=2;i<=m;++i) {

		int x = 2*i, y = 2*i+1;	// i次选取的最后两个数

		for(int k=1;k<x;++k) {	//枚举上一次留下的数

			f[i][x] = min(f[i][x], f[i-1][k]+Const(y,k));

			f[i][y] = min(f[i][y], f[i-1][k]+Const(x,k));

			f[i][k] = min(f[i][k], f[i-1][k]+Const(x,y));

		}

	}

	int ans = f[m][n+1];

	printf("%d\n",ans);

	return 0;

}

update

加上路径记录版

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define INF 0x3f3f3f3f

using namespace std;

inline int read() {

	int x=0,f=1; char ch=getchar();

	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }

	while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }

	return x * f;

}

const int N = 1007;

int n;

int a[N];

int f[N][N];

struct operation {

	int x,y,pre;

}p[N][N];

inline int Const(int x,int y) {

	return max(a[x], a[y]);

}

void output(int now,int pos) {

	if(now == 0) return ;

	output(now-1,p[now][pos].pre);

	if(a[p[now][pos].x])

		printf("%d ",p[now][pos].x);

	if(a[p[now][pos].y])

		printf("%d",p[now][pos].y);

	puts("");

}

int main()

{

	n = read();

	for(int i=1;i<=n;++i)

		a[i] = read();

	memset(f, 0x3f, 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]);

	p[1][1] = (operation)<%2,3,0%>;

	p[1][2] = (operation)<%1,3,0%>;

	p[1][3] = (operation)<%1,2,0%>;

	int m = n&1 ? n/2+1 : n/2;

	for(int i=2;i<=m;++i) {

		int x = 2*i, y = 2*i+1;	// i次选取的最后两个数

		for(int k=1;k<x;++k) {	//枚举上一次留下的数

			if(f[i-1][k]+Const(y,k) < f[i][x]) {

				f[i][x] = f[i-1][k]+Const(y,k);

				p[i][x] = (operation)<%k,y,k%>;

			}

			if(f[i-1][k]+Const(x,k) < f[i][y]) {

				f[i][y] = f[i-1][k]+Const(x,k);

				p[i][y] = (operation)<%k,x,k%>;

			}

			if(f[i-1][k]+Const(x,y) < f[i][k]) {

				f[i][k] = f[i-1][k]+Const(x,y);

				p[i][k] = (operation)<%x,y,k%>;

			}

			// f[i][x] = min(f[i][x], f[i-1][k]+Const(y,k));

			// f[i][y] = min(f[i][y], f[i-1][k]+Const(x,k));

			// f[i][k] = min(f[i][k], f[i-1][k]+Const(x,y));

		}

	}

	int ans = f[m][n+1];

	printf("%d\n",ans);

	output(m,n+1);

	return 0;

}

巴特西

CF 82 D.Two out of Three

前言

最新文章

热门文章