比较好的构造题
首先数据范围为 \(18\) ，令人浮想联翩：状压
有一个性质就是我们可以在一定操作内把一段区间的数全部变成 \(0\) ~ \(r-l\) ，再全部变成 \(r-l+1\)
具体的，对于一段区间 \(l,r\) 变成 \(0\) ~ \((r-l+1)\)
- 先把 \(l,r-1\) 变为 \(0\) ~ \((r-l)\) ,
- 然后判断 \(a_r\) 是否是 \(r-l+1\)，如果 不是 则把 \(l,r\) 全都变成 \(r-l+1\) ，
- 然后再把 \(l,r-1\) 变为 \(0\) ~ \((r-l)\) 但是要注意，这一次变的过程不能再进行第 \(2\) 步，因为这个区间所有数已经变成了 \(r-l+1\)
void dfs(int l,int r,int f)
{
if(l==r)
{
if(f==0||a[l]!=0) put.push_back({l+1,r+1});
return;
}
dfs(l,r-1,f);
if(f==0||a[r]!=r-l)
{
put.push_back({l+1,r+1});
dfs(l,r-1,0);
}
}
继续分析问题，发现有一些数变更划算，有些数不变更划算，列如 \(1000\) 这个数
发现不方便直接贪心看每个数是否变，所以考虑二进制枚举不变的数，剩下的数要变
再次发现对于一段完整的要变的区间，一起变显然更有性价比
即不变的数把原序列分割成了多个区间，对于每个要变区间进行变换
则问题得到解决
#include<bits/stdc++.h>
using namespace std;
const int N=19;
int a[N];
vector<pair<int,int> > put;
void dfs(int l,int r,int f)
{
if(l==r)
{
if(f==0||a[l]!=0) put.push_back({l+1,r+1});
return;
}
dfs(l,r-1,f);
if(f==0||a[r]!=r-l)
{
put.push_back({l+1,r+1});
dfs(l,r-1,0);
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
int ans=0;
int id=0;
for(int i=0;i<(1<<n);i++)
{
int cnt=0;
for(int j=0;j<n;j++)
{
if(i>>j&1) cnt+=a[j];
else
{
int k=j;
while(k<n&&!(i>>k&1)) k++;
cnt+=(k-j)*(k-j);
j=k-1;
}
}
if(ans<cnt)
{
ans=cnt;
id=i;
}
}
//cout<<id<<"\n";
for(int i=0;i<n;i++)
{
if(!(id>>i&1))
{
int j=i;
while(j<n&&!(id>>j&1))
{
j++;
}
//cout<<i<<" "<<j<<"\n";
dfs(i,j-1,1);
put.push_back({i+1,j});
i=j-1;
}
}
cout<<ans<<" "<<put.size()<<"\n";
for(auto i:put) printf("%d %d\n",i.first,i.second);
}