B.小红的子序列(dp)()-其他

B.小红的子序列(dp)()

B.小红的子序列(dp)

题目链接

自序列问题一般是dp问题，这里结尾dp状态只有四种，蓝偶，红偶，蓝奇，红奇。对于当前物品，所要做的判断就是加与不加入状态完全相反的背包中，例如，当前是蓝色偶数，现在就要判断加不加到当前以红色奇数为结尾的数组中，状态方程：

f[c[i][a[i]&1]=max(f[c[i]][a[i]&1],f[1-c[i]][1-(a[i]&1)]+(LL)a[i]);

// Problem: 小红的子序列
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11251/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=2e5+10;
int a[N],n;
string col;
int c[N];
LL f[2][2];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	cin>>col;
	for(int i=0;i<n;i++){
		c[i+1]=(col[i]=='R');
	}
	for(int i=1;i<=n;i++){
		f[c[i]][a[i]&1]=max(f[c[i]][a[i]&1],f[1-c[i]][1-(a[i]&1)]+(LL)a[i]);
	}
	LL ans=0;
	 for(int i=0;i<2;i++){
		 for(int j=0;j<2;j++){
			 ans=max(f[i][j],ans);
			 // cout<<f[i][j]<<" ";
			}
	}
	printf("%lld",ans);
	
	

	return 0;
}

B.小红的子序列(dp)

题目链接

自序列问题一般是dp问题，这里结尾dp状态只有四种，蓝偶，红偶，蓝奇，红奇。对于当前物品，所要做的判断就是加与不加入状态完全相反的背包中，例如，当前是蓝色偶数，现在就要判断加不加到当前以红色奇数为结尾的数组中，状态方程：

f[c[i][a[i]&1]=max(f[c[i]][a[i]&1],f[1-c[i]][1-(a[i]&1)]+(LL)a[i]);

// Problem: 小红的子序列
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11251/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=2e5+10;
int a[N],n;
string col;
int c[N];
LL f[2][2];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	cin>>col;
	for(int i=0;i<n;i++){
		c[i+1]=(col[i]=='R');
	}
	for(int i=1;i<=n;i++){
		f[c[i]][a[i]&1]=max(f[c[i]][a[i]&1],f[1-c[i]][1-(a[i]&1)]+(LL)a[i]);
	}
	LL ans=0;
	 for(int i=0;i<2;i++){
		 for(int j=0;j<2;j++){
			 ans=max(f[i][j],ans);
			 // cout<<f[i][j]<<" ";
			}
	}
	printf("%lld",ans);
	
	

	return 0;
}