2014 ACM/ICPC
Asia Regional Xi'an Online

对于N个数 n(1 ≤ n ≤ 5×10⁴),

把N个数分成随意个区间，每一个区间的值是该区间内不同数字个数的平方和，答案使和最小

DP思路，首先要对数据合并相连同样数字，然后离散化。

数据太弱了。。。。

。

然后直接做N*N的DP居然能AC。

。

。。比赛时候想到了。。

。不敢写。

。。

G++AC C++TLE

#include "stdio.h"

#include "string.h"

#include "queue"

#include "iostream"

#include "algorithm"

using namespace std;

const int inf = 0x3f3f3f3f;

struct node

{

    int x,id,v;

}a[50000];

int dp[50010],vis[50010];

vector<int>q;

bool cmpx(node a,node b)

{

    return a.x<b.x;

}

bool cmpid(node a,node b)

{

    return a.id<b.id;

}

int Min(int a,int b)

{

    if (a<b) return a;

    else return b;

}

int main()

{

    int n,m,i,j,temp,x,cnt;

    while (scanf("%d",&n)!=EOF)

    {

        m=1;

        scanf("%d",&a[1].x);

        a[1].id=1;

        for (i=2;i<=n;i++)

        {

            scanf("%d",&x);

            if (x!=a[m].x)

            {

                a[++m].x=x;

                a[m].id=m;

            }

        } // 合并相邻同样数字

        n=m;

        sort(a+1,a+1+n,cmpx);

        temp=1;

        a[1].v=1;

        for (i=2;i<=n;i++)

        {

            if (a[i].x!=a[i-1].x) temp++;

            a[i].v=temp;

        } // 离散化

        sort(a+1,a+1+n,cmpid);

        memset(dp,inf,sizeof(dp));

        dp[0]=0;

        dp[n]=n;

        memset(vis,0,sizeof(vis));

        for (i=0;i<n;i++)

        {

            if (dp[i]>dp[i+1]) continue;

            cnt=0;

            for (j=i+1;j<=n;j++)

            {

                if (vis[a[j].v]==0)

                {

                    cnt++;

                    q.push_back(a[j].v);

                    vis[a[j].v]=1;

                }

                if (dp[i]+cnt*cnt>=dp[n]) break; // 小优化，大于DP[n] 直接退出

                dp[j]=Min(dp[j],dp[i]+cnt*cnt);

            }

            for (j=0;j<q.size();j++)

                vis[q[j]]=0;

            q.clear();

        }

        printf("%d\n",dp[n]);

    }

    return 0;

}