[CSP-S模拟测试]:打扫卫生（暴力）

题目描述

有$N$头奶牛，每头那牛都有一个标号$P_i1\leqslant Pi\leqslant M\leqslant N\leqslant 40,000$。现在$Farmer\ John$要把这些奶牛分成若干段，定义每段的不河蟹度为：若这段里有$k$个不同的数，那不河蟹度为$k\times k$。那总的不河蟹度就是所有段的不河蟹度的总和。

输入格式

第一行：两个整数$N,M$
第$2..N+1$行：$N$个整数代表每个奶牛的编号

输出格式

一个整数，代表最小不河蟹度

样例

样例输入：

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4

样例输出：

数据范围与提示

对于$30\%$的数据，$1\leqslant M\leqslant N\leqslant 100$。
对于另外$20\%$的数据，$1\leqslant M\leqslant N\leqslant 5,000$。
对于$100\%$的数据，$1\leqslant P_i,\leqslant M\leqslant N\leqslant 40,000$。

题解

正解我不会，$n^2$暴力有人听吗？

对于当前处理的点$i$，我们从后往前扫，如果当前这段不一样的数比$i$大，那么肯定不会有贡献，剪掉就好了，于是它$A$了……

时间复杂度：$\Theta(n^2)$。

期望得分：$50$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,m;

int a[40001];

int dp[40001];

bool vis[40001];

int main()

{

	scanf("%d%d",&n,&m);

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

		scanf("%d",&a[i]);

	for(int i=1;i<=n;i++)dp[i]=i;

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

	{

		int sum=0;

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

		for(int j=i;j;j--)

		{

			if(!vis[a[j]]){sum++;vis[a[j]]=1;}

			if(sum*sum>=i)break;

			if(dp[i]>dp[j-1]+sum*sum)dp[i]=dp[j-1]+sum*sum;

		}

	}

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

	return 0;

}

rp++

巴特西