U447601 星月的建筑游戏题解

题目链接

解题思路

solution1

动态规划题目，略微复杂。

状态非常好设计，设 $f_i$表示使用前i个木棍可以获得的最大积分。

然后暴力枚举来选择建筑材料的区间$[i+1,j]$,接着就在这个区间中枚举$a,b,c$(其实就是三边长),用积分计算公式($f_i+16 \times S^2 $) 更新状态即可。

时间复杂度 $O(n^5)$,直接拿捏20分

solution2

上述思路为何慢呢？打出了代码的大佬应该可以发现,上述思路使用了两个dp来维护转移，那么，简化dp即可减小时间复杂度

想到这一点之后，我们就可以用余弦定理从小到大枚举$l$,然后再枚举r，并维护一个set记录$[l+1,r-1]$区间内所有的$c^2$(具体意义看一下题面),然后直接用upper_bound/lower_bound找到$a^2+b^2$的前去后计算面积并更新dp的值，

每次r+1的时候再把$a_r^2$放入Set种即可。当然这只有75分

核心代码:

for(int i=1;i<=n;i++)
{
f[i]=max(f[i],f[i-1]);
set<int>s;
for(int j=i+1;j<=n;j++)
{
auto it=s.lower_bound(a[i]*a[i]+a[j]*a[j]);
if(it!=s.end())
f[j]=max(f[j],f[i-1]+calc(a[i],a[j],sqrt(*it)+0.5));
if(it!=s.begin())
f[j]=max(f[j],f[i1]+calc(a[i],a[j],sqrt(*prev(it))+0.5));
s.insert(a[j]*a[j]);
}//calc是计算三角形面积的函数 
}

Solution3

这个当然是正解了

我们还是先枚举(废话) ，那么每⼀轮要做的事情就是在$r$之前找到$\le a_l^2+a_r2 $最⼤的$a_i^2$ 。

如果我们从后往前枚举$r$，那么只需要找到⼀个数据结构⽀持单点删除，查询$\le x$最⼤的⼀个。

这个是可以⽤并查集维护的。

具体难以口述请见代码:

#include<bits/stdc++.h>
using namespace std;
using ll=__int128;
#define all(a) (a).begin(),(a).end()
const int N=8e3+10;
const ll INF=4e18;
long long n,a[N],b[N],cur[N],fa[N];
long long k,p[N],lim[N],rk[N];
ll f[N];
int find(long long x)//调用并查集 
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
ll calc(int a,int b,int c)
{//计算面积的函数 
if(max({a,b,c})*2>=a+b+c)
return -INF;
return 1ll*(a+b+c)*(b+c-a)*(c+a-b)*(a+b-c);
}
bool cmp(long long &x,long long &y)//&不能忘！！！ 
{
return b[x]<b[y];
}
std::ostream& operator << (std::ostream &out,__int128 a){
if(a<0)out<<'-',a=-a;
if(a>9)out<<a/10;
return out<<int(a%10);
}//题目已经弱化，可以不写
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],b[i]=a[i]*a[i];
iota(cur,cur+1+n,0);//生成递增序列 不懂问度娘 
sort(cur+1,cur+1+n,cmp);
fill(f,f+1+n,-INF),f[0]=0;
for(int i=1;i<=n;i++)
{
f[i]=max(f[i],f[i-1]);
k=0;
for(int j=1;j<=n;j++)
if(cur[j]>i)
p[rk[cur[j]]=++k]=cur[j];
for(int j=1,x=1;j<=k;j++)
{
for(;x<=k&&b[p[x]]<=b[i]+b[p[j]];x++);
lim[p[j]]=x;
}
iota(fa,fa+1+k,0);
for(int j=n;j>i;j--)//核心部分1 
{
fa[rk[j]]=find(rk[j]-1);
int x=find(lim[j]-1);//调用并查集 
if(x)
f[j]=max(f[j],f[i-1]+calc(a[i],a[p[x]],a[j]));//状态转移 
}
iota(fa,fa+1+k,0);
fa[k+1]=0;
for(int j=n;j>i;j--)//核心部分2 
{
fa[rk[j]]=find(rk[j]+1);
int x=find(lim[j]);//调用并查集+1
if(x)
f[j]=max(f[j],f[i-1]+calc(a[i],a[p[x]],a[j]));//状态转移 
}
}
std::cout<<f[n]<<std::endl;//理解为cout<<f[n];
return 0;
}

原文地址：https://blog.csdn.net/daihaoweikevin/article/details/140558861

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！