关于昨天晚上CF的C题

乱搞一通，思路是暴力枚举一个

i

点，让

p_j=j(j<i)

，

p_j=n+i-j(j\geq i)

，求答案。效率

O(n^2)

，不能保证正确性。

最后居然过了。

下面是代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int t;
int main()
{
	cin>>t;
	while(t--)
	{
		int n,ans=0;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			int mx=0,sum=0;
			for(int j=1;j<i;j++)
			{
				sum+=j*j;
				mx=max(mx,j*j);
			}
			for(int j=i;j<=n;j++)
			{
				sum+=j*(n+i-j);
				mx=max(mx,j*(n+i-j));
			}
			ans=max(ans,sum-mx);
		}
		cout<<ans<<endl;
	}
	return 0;
}

可以证明我这种做法的正确性吗，以及正解是啥/yiw

关于昨天晚上CF的C题

讨论操作

回复

相关推荐

关于昨天晚上CF的C题