NWERC 2019 Kitesurfing

有一点神，结合了代码才理解到了它的精妙之处！

考虑研究我们的解的形态，并尝试将其规范化。

显然，我们的解当中必然存在一连串的大跳，然后接一段游泳小跳啥的，然后继续大跳啥的。

假如中间只接了游泳，那么考虑将这段游泳和后面的大跳交换位置，发现最终落点不变，但中间落点不一定合法。

如果中间落点不合法，则我们完全可以把部分游泳移动使之大跳落点恰好在岛屿的右边界。

如果合法则递归考虑。

假如中间直接了小跳，则小跳一定可以变大，让落点不变只需要让后面的跳跃同时缩短即可，发现这样做不仅会使答案不劣而且很有可能使它更优。

由于小跳是小跳，因此这个小跳一定可以恰好落在岛屿的左端点。

如果小跳和游泳同时连续存在，则小跳可以变大直到无游泳或大跳，则必然更优且划归为上述情况。

整理以上讨论可以得到：

存在最优解由以下结构构成：

1.不断大跳，然后游一段泳，然后大跳到一个岛屿右端点。

2.不断大跳，然后小跳到一个岛屿左端点，然后下一跳尽量跳远一点。

于是我们可以通过上述规则转移。

考虑对以每一个岛屿边缘为起点跳到以另一个岛屿的边缘为一次转移，由于最多只会有两种到达情况，因此总转移数是 \(O(n)\) 的，因此总复杂度是 \(O(n^2)\) 的。

为了实现轻松，我们可以让每一个转移，即大跳过下一个岛屿也作为状态，把状态数升为 \(n^2\) ，会好写很多。

官方题解说复杂度是 \(O(n^3)\) 的，但我觉得是 \(O(n^2log n)\) 的，但机房有人不信，有兴趣的同学可以精细实现。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define pii pair 
#define mp make_pair
#define fs first
#define sc second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

//const int Mxdt=100000; 
//static char buf[Mxdt],*p1=buf,*p2=buf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;

template 
void read(T &x) {
	T f=1;x=0;char s=getchar();
	while(s<'0'||s>'9') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=(x<<3)+(x<<1)+(s-'0');s=getchar();}
	x *= f;
}

template 
void write(T x , char s='\n') {
	if(!x) {putchar('0');putchar(s);return;}
	if(x<0) {putchar('-');x=-x;}
	T tmp[25]={},t=0;
	while(x) tmp[t++]=x%10,x/=10;
	while(t-->0) putchar(tmp[t]+'0');
	putchar(s); 
}

map  S;
pii R[505];
LL s , d , t , n;

int main() {
//	freopen("data.in" , "r" , stdin);
//	freopen("mine.out" , "w" , stdout);
	read(s),read(d),read(t);
	read(n);
	R[0] = mp(0 , 0);
	for (int i = 1; i <= n; ++i) read(R[i].fs),read(R[i].sc);
	
	S[0] = 0;
	LL ans = 1e18;
	while(!S.empty()) {
		LL x = S.begin()->fs , val = (S.begin())->sc;
//		write(x , ' ') , write(val);
		S.erase(S.begin());
		if(x >= R[n].sc) {
			if(x > s) x = s;
			ans = min(ans , val + (s - x) / d * min(t , d) + min(t , s - x - (s - x) / d * d));
			continue;
		} 
		
		for (int i = 1; i <= n; ++i) if(R[i].fs >= x) {
			LL cnt = (R[i].fs + 1 - x + d - 1) / d;
			int id = 0; 
			for (int j = 1; j <= n; ++j) {
				if(R[j].fs < cnt * d + x && cnt * d + x < R[j].sc) {
					id = j;
					break;
				}
			} // 判断是否跳过最近的岛屿后撞别的岛屿上了。如果撞上就只能跳到它的左端点。这个部分用set精细实现后复杂度应该可以降到 n^2 logn
			if(!id) {
				if(!S.count(cnt * d + x)) S[cnt * d + x] = 1e18;
				S[cnt * d + x] = min(S[cnt * d + x] , val + cnt * t);
			}
			else {
				if(!S.count(R[id].fs)) S[R[id].fs] = 1e18;
				S[R[id].fs] = min(S[R[id].fs] , val + cnt * t);
			}
			
			for (int j = i; j <= n; ++j) 
				if(R[j].sc - d <= R[i].fs) {
					if(!S.count(R[j].sc)) S[R[j].sc] = 1e18;
					LL len = R[j].sc - d - x;
					len = max(len , 0ll);
					S[R[j].sc] = min(S[R[j].sc] , val + t + len / d * min(d , t) + min(len % d , t));
				}
				else break; // 跑一段平路，然后跳到岛屿右端点。
			
			break;
		}
	}
	write(ans);
	return 0;
}

相关

标签