codeforces Simba on the Circle (dp)

Simba on the Circle

 题意：长度为n的环，第i个数字为ai。 从起点s出发，走一个格子的花费为1，输出当前数字的花费为0，输出n个数的非递减序列的最小花费是多少，并打印方案。

若ai都不相同的话就很好做了，考虑值相同的ai作为一段，其中肯定有一个起点和终点，即这一段第一个走的i和最后一个走的i，从起点向同一个方向走到终点走完所有ai肯定是最优的。（终点就在起点旁边→_→）

dp1[i]表示以i为起点，走值相同的ai，的答案

dp2[i]表示以i为终点

转移：

dp2[i] = min(dp1[j] + dis[i][j]),  aj为比ai大的最小的一个

如果ai相同的只有一个，dp1[i] = dp2[i]

否则, dp1[i] = min(dp2[j] + cd[i][j]),  ai = aj注意方向大概要走一圈的样子

边界 dp2[i] = 0 (ai = max)

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;

#define LL long long
#define N 2010
#define M 200020
#define inf (1100000000)
#define ls (i << 1)
#define rs (ls | 1)
#define md (ll + rr >> 1)
#define lson ll, md, ls
#define rson md + 1, rr, rs

int d[N][N], cd[N][N], dp1[N], dp2[N];
int nxt[N], a[N];
int n, s;
int gao2(int u) ;
int gao1(int u);

int gao2(int u) {
	int &res = dp2[u];
	if(res != -1) return res;
	if(nxt[u] == inf) return res = 0;
	res = inf;
	for(int i = 0; i < n; ++i) {
		if(a[i] == nxt[u]) {
			res = min(res, gao1(i) + d[u][i]);
		}
	}
	//printf("dp2[%d] %d\n", u, dp2[u]);
	return res;
}

int gao1(int u) {
	int &res = dp1[u];
	if(res != -1) return res;
	res = inf;
	for(int dir = -1; dir <= 1; dir += 2) {
		int v = -1;
		for(int i = 1; i < n; ++i) {
			int t = (u + dir * i + n ) % n;
			if(a[t] == a[u]) {
				v = t;
				break;
			}
		}
		if(v == -1)
			res = min(res, gao2(u));
		else {
			int add = dir == -1 ? cd[u][v] : cd[v][u];
			res = min(res, gao2(v) + add);
		}
	}
	//printf("dp1[%d] %d\n", u, dp1[u]);
	return res;
}
void output1(int u);
void output2(int u);

void output2(int u){
	int res = inf;
	if(nxt[u] == inf) return ;
	for(int i = 0; i < n; ++i) {
		if(a[i] == nxt[u]) {
			res = min(res, dp1[i] + d[u][i]);
		}
		if(res == dp2[u]) {
			printf("%c%d\n", (i-u+n)%n == d[u][i] ? '+' : '-', d[u][i]);
			output1(i);
			return ;
		}
	}
}
void output1(int u) {
	int res = inf;
	for(int dir = -1; dir <= 1; dir += 2) {
		int v = -1;
		for(int i = 1; i < n; ++i) {
			int t = (u + dir * i + n ) % n;
			if(a[t] == a[u]) {
				v = t;
				break;
			}
		}
		if(v == -1)
			res = min(res, dp2[u]);
		else {
			int add = dir == -1 ? cd[u][v] : cd[v][u];
			res = min(res, dp2[v] + add);
		}
		if(res == dp1[u]) {
			int last = 0;
			dir = (dir == -1 ? 1 : -1);
			for(int i = 1; i < n; ++i) {
				int t = (u + dir*i + n) % n;
				if(a[t] == a[u] || t == v) {
					printf("%c%d\n", dir == -1 ? '-' : '+', i-last);
					last = i;
				}
			}
			if(v == -1) output2(u);
			else output2(v);
			return ;
		}
	}
}
int main() { 
	//freopen("in.txt", "r", stdin);
	scanf("%d%d", &n, &s);
	--s;
	int mi = inf;
	for(int i = 0; i < n; ++i)
		scanf("%d", &a[i]), mi = min(mi, a[i]);
	for(int i = 0; i < n; ++i) {
		nxt[i] = inf;
		for(int j = 0; j < n; ++j) {
			if(a[j] > a[i])
				nxt[i] = min(nxt[i], a[j]);
		}
	}
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			d[i][j] = min(abs(i-j), n-abs(i-j));
			cd[i][j] = j >= i ? j - i : n - (i-j);
		}
	}

	memset(dp1, -1, sizeof dp1);
	memset(dp2, -1, sizeof dp2);
	int ans = inf;
	for(int i = 0; i < n; ++i) {
		if(a[i] == mi)
		ans = min(ans, gao1(i) + d[i][s]);
	}
	printf("%d\n", ans);
	int res = inf;
	for(int i = 0; i < n; ++i) {
		if(a[i] == mi)  {
			res = min(res, dp1[i] + d[i][s]);
			if(res == ans) {
				printf("%c%d\n", (i-s+n)%n == d[s][i] ? '+' : '-', d[s][i]);
				output1(i);
				return 0;
			}
		}
	}
}