首先可以想到一个贪心的方法，然后一层一层的合并。
也可以采用动态规划的方式，为了写起来好写，把点数*2+1，然后发现在本机上跑不过1500的数据。
交上去居然A掉了。
贪心
#include <cstdio>
#define F(i,j,k) for (int i=j;i<=k;++i)
int main()
{
int n,m,a;
scanf("%d",&n); a=0; m=n+1;
F(i,0,30) a+=(m>>i)&1; printf("%d\n",a-1);
a=0; m=n+1;
while (m>1)
{
if (m==2) a++,m=1;
else
{
switch(m%4)
{
case 1: a+=m/4*2-1;m/=4;m++;break;
case 2: a+=m/4*2; m/=4;m++;break;
case 3: a+=m/4*2+1;m/=4;m++;break;
case 0: a+=m/4*2; m/=4; break;
}
}
}
printf("%d\n",a);
}
动态规划
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define inf 0x3f3f3f3f
#define dinf -1044266559
int dp[5005][31][2],n,ans;// siz hiblack red/black
int main()
{
scanf("%d",&n); n=n*2+1;
memset(dp,0x3f,sizeof dp);
dp[1][1][1]=0;
for (int i=2;i<=n;++i)
for (int j=1;j<=i;++j)
{
if ((1<<j)>(n<<2)) break;
for (int k=1;k<=i-1;++k)
{
dp[i][j][0]=min(dp[i][j][0],dp[k][j][1]+dp[i-k-1][j][1]+1);
dp[i][j][1]=min(dp[i][j][1],dp[k][j-1][1]+dp[i-k-1][j-1][1]);
dp[i][j][1]=min(dp[i][j][1],dp[k][j-1][0]+dp[i-k-1][j-1][1]);
dp[i][j][1]=min(dp[i][j][1],dp[k][j-1][1]+dp[i-k-1][j-1][0]);
dp[i][j][1]=min(dp[i][j][1],dp[k][j-1][0]+dp[i-k-1][j-1][0]);
}
}
ans=inf;
F(i,0,n) ans=min(ans,min(dp[n][i][1],dp[n][i][0]));
printf("%d\n",ans); memset(dp,-0x3f,sizeof dp);
dp[1][1][1]=0;
for (int i=2;i<=n;++i)
for (int j=1;j<=i;++j)
{
if ((1<<j)>(n<<2)) break;
for (int k=1;k<=i-1;++k)
{
dp[i][j][0]=max(dp[i][j][0],dp[k][j][1]+dp[i-k-1][j][1]+1);
dp[i][j][1]=max(dp[i][j][1],dp[k][j-1][1]+dp[i-k-1][j-1][1]);
dp[i][j][1]=max(dp[i][j][1],dp[k][j-1][0]+dp[i-k-1][j-1][1]);
dp[i][j][1]=max(dp[i][j][1],dp[k][j-1][1]+dp[i-k-1][j-1][0]);
dp[i][j][1]=max(dp[i][j][1],dp[k][j-1][0]+dp[i-k-1][j-1][0]);
}
}
ans=0;
F(i,0,n) ans=max(ans,max(dp[n][i][1],dp[n][i][0]));
printf("%d\n",ans);
}