BZOJ 1806 IOI2007 Miners 矿工配餐 动态规划

BZOJ 1806 IOI2007 Miners 矿工配餐 动态规划

大家好,又见面了,我是全栈君。

题目大意:将一个123序列拆分为两个子序列。定义每一个数的贡献值为以这个数结尾的长度最大为3的子串中不同数的数量,求贡献值和的最大值

令f[i][a1][a2][b1][b2]为前i个数分成两组,第一组以a1 a2结尾,第二组以b1 b2结尾的最大贡献值 转移啥的自己YY吧 记得开滚动数组

尼玛写错个參数都要调半天……

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,ans,f[2][4][4][4][4];
inline int Get_Char()
{
	char c;
	do c=getchar(); while(c!='M'&&c!='F'&&c!='B');
	switch(c)
	{
		case 'M':return 1;
		case 'F':return 2;
		case 'B':return 3;
	}
}
inline int Score(int x,int y)
{
	if(x==0) return 1;
	return x==y?1:2;
}
inline int Score(int x,int y,int z)
{
	int temp=x*y*z;
	switch(temp)
	{
		case 6:return 3;
		case 1:
		case 8:
		case 27:return 1;
		case 0:return Score(y,z);
		default: return 2;
	}
}
int main()
{
	int i,a1,a2,b1,b2;
	cin>>n;
	memset(f,0xef,sizeof f);
	f[0][0][0][0][0]=0;
	for(i=1;i<=n;i++)
	{
		int temp=Get_Char();
		memset(f+(i&1),0xef,sizeof(f)>>1);
		for(a1=0;a1<=3;a1++)
			for(a2=(a1?1:0);a2<=3;a2++)
				for(b1=0;b1<=3;b1++)
					for(b2=(b1?

1:0);b2<=3;b2++) if(f[~i&1][a1][a2][b1][b2]>=0) { f[i&1][a2][temp][b1][b2]=max(f[i&1][a2][temp][b1][b2] ,f[~i&1][a1][a2][b1][b2]+Score(a1,a2,temp)); f[i&1][a1][a2][b2][temp]=max(f[i&1][a1][a2][b2][temp] ,f[~i&1][a1][a2][b1][b2]+Score(b1,b2,temp)); } } for(a1=0;a1<=3;a1++) for(a2=(a1?1:0);a2<=3;a2++) for(b1=0;b1<=3;b1++) for(b2=(b1?1:0);b2<=3;b2++) ans=max(ans,f[n&1][a1][a2][b1][b2]); cout<<ans<<endl;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115577.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ResNet34_resnetv2

    ResNet34_resnetv2pytorch版本:https://blog.csdn.net/github_36923418/article/details/83273107keras版本:https://blog.csdn.net/m0_37477175/article/details/83861678

  • 令牌桶的实现_C语言实现栈

    令牌桶的实现_C语言实现栈接上篇。Guava的令牌桶的实现中,包括一条设计哲学,需要大家注意:它允许瞬间的流量波峰超过QPS,但瞬间过后的请求将会等待较长的时间来缓解上次的波峰,以使得平均的QPS等于预定值。RateLimiter类提供了令牌桶的接口,它是一个抽象类,其子类有SmoothRateLimiter(也是个抽象类)以及孙子类SmoothBursty,SmoothWarmingUp。SmoothRateLimite…

  • 简单探讨spring整合mybatis时sqlSession不需要释放关闭的问题

    简单探讨spring整合mybatis时sqlSession不需要释放关闭的问题近期,在使用spring和mybatis框架编写代码时,sqlSession不需要手动关闭这一点引起了我的兴趣。我们都知道,单独使用mybatis时,sqlSeesion使用完毕后是需要进行手动关闭的,但为什么在和spring整合后就不需要了呢?在查阅了资料后得知,这是使用了spring中的AOP面向切面编程和动态代理技术。但是我认为脱离代码谈技术就是耍流氓。因此,我对MyBatis-Spr…

  • 软测试综述——PV操作

    软测试综述——PV操作

  • json localdatetime时间格式化无效问题

    json localdatetime时间格式化无效问题

  • -2147467259数据库操作错误!

    -2147467259数据库操作错误!没事说搭建个asp的网站,下载了个aspcms源码系统。搭建出现的主要问题是:登录后台的时候提示:-2147467259数据库操作错误!怎么解决?搜索了一下,有些说得是那么个意思,可是我的电脑环境也有些特殊情况。(比如:文件夹属性中没有“安全”选项卡)下面整理下:-21474672

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号