codeforces1130 B C D

B. Two Cakes

C. Connect

D2. Toy Train

B. Two Cakes

有一个长度为2*n的数列里面有1-n 每个数字各两个顺序是乱的

求两条1到n的最短路径之和每个数字只能用一次

题解：

p[x][0/1] 为左边的x的位置和右边的x的位置

f[i][0/1]为前i层蛋糕，第一个人到更靠左/右的i位置（相对的，第二个人就去另一个位置），所需要的最小花费

/*
Algorithm:动态规划
Author: anthony1314
Creat Time:2019.3.3
Complexity: 62 ms   3100 KB
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
#include<bits/stdc++.h>

#define ll long long
#define maxn 100005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
ll p[maxn][2], f[maxn][2];

int main() {
	ll n;
	cin>>n;
	ll x;
	memset(p,0, sizeof(p));
	memset(f,0, sizeof(f));
	for(int i = 1; i <= 2*n; i++) {
		scanf("%lld", &x);
		if(p[x][0]) {
			p[x][1] = i;
		} else {
			p[x][0] = i;
		}

	}
	p[0][1] = p[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		f[i][1] = min(f[i-1][1] + abs(p[i-1][0] - p[i][0]) + abs(p[i-1][1] - p[i][1]), f[i-1][0] + abs(p[i-1][0] - p[i][1]) + abs(p[i-1][1] - p[i][0]));
		f[i][0] = min(f[i-1][0] + abs(p[i-1][0] - p[i][0]) + abs(p[i-1][1] - p[i][1]), f[i-1][1] + abs(p[i-1][0] - p[i][1]) + abs(p[i-1][1] - p[i][0]));
//		cout<<f[i][0]<<"  "<<f[i][1]<<endl;
	}
	cout<<min(f[n][0], f[n][1])<<endl;

	return 0;
}

C. Connect

给一个n*n的矩阵给一个起点和终点

矩阵中为1表示为不可通过的障碍物为0表示可以通过现在你可以打通一个隧道要你在算出打通隧道的最小距离（欧式距离）

题解：

dfs遍历跑一遍

/*
Algorithm:  dfs 
Author: anthony1314
Creat Time: 2019.3.3
Complexity: 31 ms	100 KB
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;

const int MAXN=100+2;
const int X[]= {-1,0,1,0};
const int Y[]= {0,1,0,-1};//坐标的移动
int x1,y1,x2,y2;
int N,g[MAXN][MAXN],Ans;
bool Flag[MAXN][MAXN];
char S[MAXN];

int Calc(int a,int b,int c,int d) {//欧式距离
	return (c-a)*(c-a)+(d-b)*(d-b);
}

bool Check(int x,int y) {//检查是否越界
	if(!x || !y) return 0;
	if(x>N || y>N) return 0;
	if(Flag[x][y]) return 0;
	return g[x][y]!=1;//不越界则标记为1
}

void DFS(int x,int y,int t) {
	if(t==-1 && x==x2 && y==y2) {//不用打通道直接退出
		cout << 0 << endl;
		exit(0);
	}

	Flag[x][y]=1,g[x][y]=t;
	for(int i=0,tx,ty; i<4; i++) {
		tx=x+X[i],ty=y+Y[i];
		if(Check(tx,ty)) DFS(tx,ty,t);
	}
}

int main() {
	cin >> N;
	cin >> x1 >> y1 >> x2 >> y2;
	for(int i=1; i<=N; i++) {
		scanf("%s",S+1);
		for(int j=1; j<=N; j++) g[i][j]=S[j]-'0';
	}

	Ans=INT_MAX;
	DFS(x1,y1,-1),DFS(x2,y2,2);

	for(int a=1; a<=N; a++)
		for(int b=1; b<=N; b++) {
			if(g[a][b]!=-1) continue;
			for(int c=1; c<=N; c++)
				for(int d=1; d<=N; d++) {
					if(g[c][d]!=2) continue;
					Ans=min(Ans,Calc(a,b,c,d));
				}
		}
	cout << Ans << endl;
	return 0;
}

D2. Toy Train

有n个火车站围成一圈火车经过每个火车站可以拿一次货物放下无数次货物

现在有m次操作要你把第x个火车站的货物运到第y个火车站

请问从每个火车站开始分别需要的最短时间为多少

题解：q[i].size()为第i个火车站要运出去的货物数量

火车无论从哪一个起点开始最后停下的地点一定是需要运的货物最多到的地点

最优时间为 min(t, Calc(i, x) + (q[j].size() - 1) * n + Calc(x, y))

/*
Algorithm:贪心 
Author: anthony1314
Creat Time:2019.3.4 
Complexity:1247ms	600 KB
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<bits/stdc++.h>
#define ll long long
#define maxn 5005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
vector<ll> q[maxn];
ll n, m, ans;
ll Calc(ll x, ll y){
	if(x == y){
		return 0;
	}
	if(y > x){
		return y - x;
	}
	return n - x + y;
}
int main() {
	cin>>n>>m;
	ll x, y;
	for(ll i = 0; i < m; i++){
		scanf("%lld%lld",&x,&y);
		q[x].push_back(y);
	}
	for(ll i = 1; i <= n; i++){
		ans = 0;
		for(ll j = 1, t = -1; j <= n; j++, t = -1){
			for(ll k = 0; k < q[j].size(); k++){
				ll ans = Calc(i, j) + (q[j].size() - 1) * n + Calc(j, q[j][k]);
				if(t == -1){
					t = ans;
				}else {
					t = min(t, ans);
				}
			}
			ans = max(ans, t);
		}
		printf("%lld ", ans);
	}
	return 0;
}