题解 P4903 【心碎】

MZY666 · 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)\}.