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;
}
标签:int,LL,小红,序列,include,dp
From: https://www.cnblogs.com/viewoverlooking/p/17229992.html