cf984e Elevator

ref我好菜啊
#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

int n, u[2005], v[2005], f[2005][11][11][11][11];

int dis(int x, int y){

	return abs(x-y);

}

int dfs(int i, int cur, int a, int b, int c){

	if(f[i][cur][a][b][c]!=-1)	return f[i][cur][a][b][c];

	int re = 0x3f3f3f3f;

	if(i>n){

		if(!a && !b && !c)	return 0;

		if(a)	re = min(re, dfs(i, a, 0, b, c)+dis(cur,a)+1);

		if(b)	re = min(re, dfs(i, b, a, 0, c)+dis(cur,b)+1);

		if(c)	re = min(re, dfs(i, c, a, b, 0)+dis(cur,c)+1);

		f[i][cur][a][b][c] = re;

		return re;

	}

	if(a)	re = min(re, dfs(i, a, 0, b, c)+dis(cur,a)+1);

	if(b)	re = min(re, dfs(i, b, a, 0, c)+dis(cur,b)+1);

	if(c)	re = min(re, dfs(i, c, a, b, 0)+dis(cur,c)+1);

	if(a && b && c){

		re = min(re, dfs(i+1, v[i], a, b, c)+dis(cur,u[i])+dis(u[i],v[i])+2);

		re = min(re, dfs(i+1, a, v[i], b, c)+dis(cur,u[i])+dis(u[i],a)+2);

		re = min(re, dfs(i+1, b, a, v[i], c)+dis(cur,u[i])+dis(u[i],b)+2);

		re = min(re, dfs(i+1, c, a, b, v[i])+dis(cur,u[i])+dis(u[i],c)+2);

	}

	else{

		if(!a)	re = min(re, dfs(i+1, u[i], v[i], b, c)+dis(cur,u[i])+1);

		else if(!b)	re = min(re, dfs(i+1, u[i], a, v[i], c)+dis(cur,u[i])+1);

		else	re = min(re, dfs(i+1, u[i], a, b, v[i])+dis(cur,u[i])+1);

	}

	f[i][cur][a][b][c] = re;

	return re;

}

int main(){

	cin>>n;

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

		scanf("%d %d", &u[i], &v[i]);

	memset(f, -1, sizeof(f));

	cout<<dfs(1, 1, 0, 0, 0)<<endl;

	return 0;

}
巴特西

cf984e Elevator

最新文章

热门文章
