脚本宝典收集整理的这篇文章主要介绍了【题解】CF1421E Swedish Heroes，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

找规律题。

不难想出区间 (rm DP) ，但是 (mathcal{O}(N^3)) 已经是信息极限了。

观察这道题的特殊性质。

我们只关注最终序列，每一个位置是否取反，所以我们打一个暴搜的代码。

#include<bITs/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define PRe(i,a,b) for(int i=a;i>=b;i--)
#define N 55
using namespace std;
int n,a[N],v[N];
void solve(int k){
	if(k == n){
		rep(i,1,n){
			if(a[i])putchar('-');
			else putchar('+');
		}
		putchar('n');
		return;
	}
	int b[N];
	rep(i,1,n)b[i] = a[i];
	rep(i,1,n-1)if(!v[i]){
		v[i] = 1;
		int j = i;
		a[i] ^= 1;a[i + 1] ^= 1;
		while(j > 1 && v[j - 1])a[--j] ^= 1;
		j = i + 1;
		while(j < n &amp;& v[j])a[++j] ^= 1;
		solve(k + 1);
		v[i] = 0;
		rep(i,1,n)a[i] = b[i];
	}
}
int main(){
	scanf("%d",&n);
	solve(1);
	return 0;
} 

输入 (n) ，得到所有可能的序列，然后我们发现这些序列的加号个数有一定的规律。

下面是表，(S) 表示加号个数的集合。

n   S
1   1
2   0
3   2
4   1,4
5   0,3
6   2,5
7   1,4,7

不难发现 ((n+sum_{+})bmod 3=2)。同时序列中必定有两个相邻的位置符号相同。

不得不说这题的样例非常良心，指出了必须存在邻项符号相同的情况。

所以我们设计状态 (f[i][0/1/2][0/1][0/1]) 表示前 (i) 个数，当前和 (bmod 3) 后的值，上一个位置是 (+/-)，是否已经有邻项相同的位置。

@R_782_1304@ (mathcal{O}(N))，转移时有 (24) 倍常数。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 200005
using namespace std;
int n,a[N];long long f[N][3][2][2];
inline void ck(long long &x,long long y){if(y > x)x = y;}
int main(){
	scanf("%d",&n);
	rep(i,1,n)scanf("%d",&a[i]);
	if(n==1){printf("%dn",a[1]);return 0;}
	memset(f,0xCF,sizeof(f));
	f[1][n % 3][0][0] = -a[1];
	f[1][(n + 1) % 3][1][0] = a[1];
	rep(i, 2, n)rep(j, 0, 2)rep(k, 0, 1)rep(p, 0, 1)rep(w, 0, 1)
		ck(f[i][(j + k) % 3][k][w | (k == p)], f[i - 1][j][p][w] + (k * 2 - 1) * a[i]);
	printf("%lldn",max(f[n][2][0][1], f[n][2][1][1]));
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的【题解】CF1421E Swedish Heroes全部内容，希望文章能够帮你解决【题解】CF1421E Swedish Heroes所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。