19-11-08-Night

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

ZJ：

喜闻乐见：

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

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

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

$kuku$

TJ解:

T1：

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

先拆环。

好像就没啥了。

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

#include <iostream>
#include <cstring>
#include <cstdio>
#define N 333using 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 111111using 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");}
}

UPD:T3不会