记录编号	39344	评测结果	AAAAAAAAAA
题目名称	磁性链	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2012-07-09 15:11:31	内存使用	0.29 MiB

#include <cstdio>
#include <climits>
 
#define I_F "linka.in"
#define O_F "linka.out"
 
const int MAXq=100+2;
 
int n, q;
int p[MAXq], s[MAXq];
int ans;
 
void Input();
template<typename Any>
inline void Swap(Any&, Any&);
void Sort();
void Prework();
inline int Min(const int&, const int&);
void Dynap();
void Output();
 
int main()
{
    Input();
    Sort();
    Prework();
    Dynap();
    Output();
    return 0;
}
 
void Input()
{
    freopen(I_F,"r",stdin);
    scanf("%d%d",&n,&q);
    for (int i=0; i<q; ++i)
        scanf("%d",&p[i]);
}
 
template<typename Any>
inline void Swap(Any &a, Any &b)
{
    Any t=a;
    a=b;
    b=t;
}
 
void Sort()
{
    for (int i=0; i<q; ++i)
        for (int j=q-1; j>i; --j)
            if (p[j]<p[j-1])
                Swap(p[j],p[j-1]);
}
 
void Prework()
{
    s[0]=0;
    for (int i=1; i<=q; ++i)
        s[i]=p[i-1]-i;
    s[q+1]=n-q;
}
 
inline int Min(const int &a, const int &b)
{
    return (a<b)?a:b;
}
 
void Dynap()
{
    int r;
    int f[MAXq][MAXq]={{0}};
    for (int i=2; i<=q+1; ++i)
        for (int j=1; j<=q-i+2; ++j)
        {
            r=j+i-1;
            f[j][r]=INT_MAX;
            for (int k=j; k<r; ++k)
                f[j][r]=Min(f[j][r],f[j][k]+f[k+1][r]);
            f[j][r]+=s[r]-s[j-1]+i-2;
        }
    ans=f[1][q+1];
}
 
void Output()
{
    freopen(O_F,"w",stdout);
    printf("%d\n",ans);
}