自动搬运

查看原文

来自洛谷，原作者为

	MZY666 「It's time to see what I can do_To test the limits and break through.」

搬运于2025-08-24 22:05:06，当前版本为作者最后更新于2020-03-03 21:21:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题传送门。 在我的博客中食用效果更佳。

本题解含证明。

这种题本蒟蒻表示并看不懂，可看输入输出这么简单，找规律就对了。

找规律过程其它题解也说过，这里跳过。

得到：心碎数= $N^2/2+1$.

Code:

#include<bits/stdc++.h>//万能头文件好
using namespace std;//这个不能少
#define ll long long//个人习惯，可以少打一点字
int main(){
    ll n;//定义
    scanf("%lld",&n);//输入
    printf("%lld",(n*n)/2+1);//输出
    return 0;//over
}

你以为这就完了?

据说，此题无人能证明其解法，而当我们扒出作者的标程后，会发现....(下面是标程)

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int n;
int f[23333],g[23333];//我忍不住来吐槽一下这个数组是真的皮
int main(){
	scanf("%d",&n);
	memset(g,0x3f,sizeof(g));
	memset(f,0x1f,sizeof(f));
	f[1]=f[2]=g[1]=0;
	g[2]=1;g[3]=2;g[4]=4;
	for(int i=3;i<=n;i++){
	for(int j=2;j<=i;j++)
	f[i]=min(f[i],f[i-j]+g[j]);
	for(int j=1;j<i;j++)
	g[i+j]=min(g[i+j],f[i]+f[j]+i*j);	
	}
	printf("%d",n*(n-1)/2-f[n]+n);
	return 0;
}

我们会发现他提交了两次。一次在比赛中提交，一次在题库中提交。

出于好奇，让我们点进比赛链接，在比赛的介绍中惊喜地发现了本题的证明！

再次说明：以下内容为作者的idea，非原创（我题解可能过不了了），只是给大家展示一下本题的正确证明方法。

------排版上略有改动------

1.心碎

手玩:$40$%；打表:$70$%：

我们发现，分的块数 = $N +$ 交点个数。

如果不考虑多线共点，交点个数恰好为逆序对数。

我们构造一个排列 $\{Ai\}$ ，则多线共点的条件为 $Ai$ 中存在三个或以上元素在同一个等差数列的对应位置上。

于是，在构造的过程中，可以从中间选择一段移到最前面。

设 $f(i)$ 表示 $i$ 个点由于多线共点至少损失的逆序对个数，则 $f(i)=min\{f(j)+f(k)+f(i-j-k)\}$.

$O(N^3)$ $100$%：在 $70$% 的基础上，设立数组 $g(i)$ 表示 $f(j)+f(i-j)$ 的最小值，则刚才的方程转化为$f(i)=min\{g(j)+f(i-j)\}$.

$O(N^2)$ 彩蛋：OEIS大法好！把前几项输进OEIS，容易得到规律：答案 = $(N \times N/2)+1$.