首页 > 其他分享 >B.小红的子序列(dp)

B.小红的子序列(dp)

时间:2023-03-18 13:44:08浏览次数:51  
标签:int LL 小红 序列 include 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;
}

标签:int,LL,小红,序列,include,dp
From: https://www.cnblogs.com/viewoverlooking/p/17229992.html

相关文章

  • R语言k-Shape时间序列聚类方法对股票价格时间序列聚类|附代码数据
    原文链接:http://tecdat.cn/?p=3726最近我们被客户要求撰写关于k-Shape时间序列聚类的研究报告,包括一些图形和统计输出。本文我们将使用k-Shape时间序列聚类方法检查与......
  • 说一下线程池内部工作原理(ThreadPoolExecutor)
    ThreadPoolExecutor构造方法的参数corePoolSize:线程池的核心线程数,说白了就是,即便是线程池里没有任何任务,也会有corePoolSize个线程在候着等任务。maximumPoolSize:最大......
  • 操作码序列
    操作码序列通常对PE格式文件(.exe文件等),用IDAPro反汇编得到对应的asm(包含汇编代码)文件。从asm文件中可以提取操作码、函数调用等信息作为特征训练机器学习和深度......
  • 【特征】操作码序列
    【特征】操作码序列通常对PE格式文件(.exe文件等),用IDAPro反汇编得到对应的asm(包含汇编代码)文件。从asm文件中可以提取操作码、函数调用等信息作为特征训练机器学......
  • 【小结】操作码序列
    【小结】操作码序列通常对PE格式文件(.exe文件等),用IDAPro反汇编得到对应的asm(包含汇编代码)文件。从asm文件中可以提取操作码、函数调用等信息作为特征训练机器学......
  • .NET Threadpool 饥渴,以及队列是如何使它更糟的
    .NETThreadpool饥渴,以及队列是如何使它更糟的.NETThreadpoolstarvation,andhowqueuingmakesitworse-CriteoEngineering已经有一些对threadpool饥渴的讨论......
  • Ubuntu中安装包时提示:you might want to run 'sudo dpkg --configure -a' to correct
    场景在Ubuntu中执行sudoapt-getinstall-ynano时提示:youmightwanttorun'sudodpkg--configure-a'tocorrecttheproblem实现按照提示输入:sudodpkg--configure......
  • 「背包DP」科技庄园
    本题为3月17日23上半学期集训每日一题中A题的题解题面题目描述Life种了一块田,里面种了有一些桃树。Life对PFT说:“我给你一定的时间去摘桃,你必须在规定的时间之内回到......
  • m基于改进遗传算法优化的双bp神经网络时间序列预测matlab仿真
    1.算法描述       遗传算法GA把问题的解表示成“染色体”,在算法中也即是以二进制编码的串。并且,在执行遗传算法之前,给出一群“染色体”,也即是假设解。然后,把这些假......
  • UDP聊天实现
    1publicclassA{2publicstaticvoidmain(String[]args)throwsIOException{3DatagramSocketsocket=newDatagramSocket(8888);4......