19-11-08-Night

再咕咕咕会被爆捶吗？？？

ZJ：

喜闻乐见：

Miemeng

01:59:43

100

01:59:44

160

01:59:44

最水的$T1$挂了？？？？

$T2$乱搞直接$A$？？？？

$T3$为什么是$0$，暴力又跪了？？

$kuku$

TJ解:

T1：

合并石子，初始化集合大小（或者打记忆化）

先拆环。

好像就没啥了。

话说我T1为什么只枚举到$n$，我明明拆环了啊？我双神志不清了？？？

#include <iostream>

#include <cstring>

#include <cstdio>

#define N 333

using namespace std;

int dp[2*N][2*N];

int arr[N*2],nn;

int val[2*N][2*N],nval[N];

int ans=0;

int vlnum(int l,int r){

	if(val[l][r])return val[l][r];

	int vn=0;

	for(int i=l;i<=r;i++){

		if(nval[arr[i]]==0)vn++;

		nval[arr[i]]++;

	}

	for(int i=l;i<=r;i++)

		nval[arr[i]]--;

	return val[l][r]=vn;

}

inline int getval(int l1,int r1,int l2,int r2){

	return vlnum(l1,r1)*vlnum(l2,r2);

}

int main(){

#ifndef LOCAL

	freopen("merge.in" ,"r",stdin);

	freopen("merge.out","w",stdout);

#endif

	scanf("%d",&nn);

	for(int i=1;i<=nn;i++){

		scanf("%d",arr+i);

		arr[nn+i]=arr[i];

	}

	for(int len=0;len<nn;len++){

		for(int l=1;l+len<=2*nn;l++){

			int r=l+len;

			for(int k=l;k<r;k++){

				dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+getval(l,k,k+1,r));

			}

		}

	}

	for(int i=1;i<=nn;i++){

		ans=max(dp[i][i+nn-1],ans);

	}

	cout<<ans<<endl;

}

T2

正解是枚举最后一嗑药，$\mathsf{ST}$表维护查询。

$\Theta(N \log N)$

这里我安利一下我的乱搞。

首先维护一个堆（以$A-B$ [上升高度] 为关键字的大根堆）「堆1」

然后再来一个（以$A$为关键字的大根堆）「堆2」

然后每次先从堆2中查一下能不能一发入魂，

如果已经嗑掉了，那么我们考虑反悔，把当时嗑掉的吐出来，用当前堆1顶的弥补一下。

如果加上弥补也上不去那就扔掉（其实这里是伪的，扔掉的有时候在后面反悔是正确的（捂脸）

如果没有嗑掉，我们试试嗑一下，如果出去了就嗑。

如果怎么都上不去，我W们M就J从堆1中取一个药并嗑掉，

如果在这时被淹死了，那一定死了，因为别的也不可能上升更高。

于是过不了对拍，

配上暴力及特殊性质食用。

于是AC了？？？

请大佬们随意Hack（汗可，亥可）：

//climb

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#define N 111111

using namespace std;

int dn,hei;

struct YW{

	int up,down;

}ys[N];

int upw[N],per[N];

int ans=0x7fffffff;

struct A_MAX{

	int up,down,id;

	A_MAX(){}

	A_MAX(const YW a,int b){up=a.up,down=a.down,id=b;}

	friend bool operator < (const A_MAX &a,const A_MAX &b){

		return a.up<b.up;

	}

};

struct Del_MAX{

	int up,down,id;

	Del_MAX(){}

	Del_MAX(const YW a,int b){up=a.up,down=a.down,id=b;}

	friend bool operator < (const Del_MAX &a,const Del_MAX &b){

		return a.up-a.down<b.up-b.down;

	}

};

bool is_del[N];

priority_queue<A_MAX>aq;

priority_queue<Del_MAX>dq;

namespace B_eq_0{

	inline bool CMP(const YW &a,const YW &b){

		return a.up>b.up;

	}

	void work(){

		sort(ys+1,ys+dn+1,CMP);

		int pos=0,wpos=0;

		for(int i=1;i<=dn;i++){

			pos+=ys[i].up;

			if(pos>=hei){

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

				return ;

			}

			wpos+=upw[i];

			if(pos<=wpos){

				puts("-1");

				return ;

			}

		}

		puts("-1");

		return ;

	}

}

namespace C_eq_0{

	void work(){

		for(int i=1;i<=dn;i++){

			aq.push(  A_MAX(ys[i],i));

			dq.push(Del_MAX(ys[i],i));

		}

		int pos=0;

		for(int i=1;i<=dn;i++){

			while(is_del[aq.top().id] && pos+aq.top().down+dq.top().up-dq.top().down < hei){

				aq.pop();

			}

			if(is_del[aq.top().id]){

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

				return;

			}

			else if(!is_del[aq.top().id] && aq.top().up+pos>=hei){

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

				return;

			}

			pos+=dq.top().up;

			pos-=dq.top().down;

			is_del[dq.top().id]=1;

			dq.pop();

		}

		puts("-1");

		return ;

	}

}

int getans(){

	int pos=0,wtpos=0;

	for(int i=1;i<=dn;i++){

		pos+=ys[per[i]].up;

		if(pos>=hei)

			return i;

		pos-=ys[per[i]].down;

		wtpos+=upw[i];

		if(pos<=wtpos)return 0x7fffffff;

	}

	return 0x7fffffff;

}

int main(){

#ifndef LOCAL

	freopen("climb.in" ,"r",stdin);

	freopen("climb.out","w",stdout);

#endif

	bool down_0=1,upw_0=1;

	scanf("%d%d",&dn,&hei);

	for(int i=1;i<=dn;i++){

		per[i]=i;

		scanf("%d%d",&ys[i].up,&ys[i].down);

		if(ys[i].down!=0)down_0=0;

	}

	for(int i=1;i<=dn;i++){

		scanf("%d",upw+i);

		if(upw[i]!=0)upw_0=0;

	}

	if(dn<=10){

		do{

			ans=min(ans,getans());

		}while(next_permutation(per+1,per+dn+1));

		printf("%d\n",ans>dn?-1:ans);

		return 0;

	}

	if(down_0)    B_eq_0::work();

	else if(upw_0)C_eq_0::work();

	else{

		for(int i=1;i<=dn;i++){

			aq.push(  A_MAX(ys[i],i));

			dq.push(Del_MAX(ys[i],i));

		}

		int pos=0,wpos=0;

		for(int i=1;i<=dn;i++){

			while(is_del[aq.top().id] && pos+aq.top().down+dq.top().up-dq.top().down < hei){

				aq.pop();

			}

			if(is_del[aq.top().id]){

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

				return 0;

			}

			else if(!is_del[aq.top().id] && aq.top().up+pos>=hei){

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

				return 0;

			}

			pos+=dq.top().up;

			if(pos>=hei){

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

				return 0;

			}

			pos-=dq.top().down;

			wpos+=upw[i];

//			cout<<pos<<" "<<wpos<<endl;

			if(pos<=wpos)break;

			is_del[dq.top().id]=1;

			dq.pop();

		}

		puts("-1");

	}

}

巴特西

19-11-08-Night

ZJ：

TJ解:

T1：

T2

UPD:T3不会

最新文章

热门文章