java学习视频 程序设计 editor aircrack-ng 劝酒文化 authentication serialization installation 河南普通话 oracle分页关键字 安卓小程序源码 js数组截取前5个 linux查询文件内容 python运行环境 destoon模板 python配置 python类和对象 python的open函数 python读取mysql数据 python基础代码 java数组添加元素 电池救星 计算机网络自顶向下 js轮播图代码 视频修复工具 小工具 js发送http请求 平面设计软件下载 什么是人肉搜索 dnf传说 ocr文字识别软件免费下载 古特里克的杀生刀 qq浏览器全屏 ipad清理内存 cad代理信息 华为悦盒怎么用 su怎么添加材质 mywi 淘宝网安卓版 三星开发者选项在哪
当前位置: 首页 > 学习教程  > 编程语言

[Rocky Mountain Regional Programming Contest 2019] Water Later

2020/9/19 14:46:58 文章标签:

题目描述:

给你一个字串,你每次可以选择一段连续的相同的字符删去,但是你以但选择了一种类型,你就必须把这个类型的所有区间段都删去,才可以考虑选下一种类型。问最少几步可以清空字串。

题目分析:

对于字符串中的种类其实是特别少的 那么我们可以枚举状态 1表示在这个状态里这种字符已经全部消去了
对于状态i来说 我们可以枚举其中消去的字符j 然后从i状态去除j的状态转移过来 现在的问题就是对于去除了j的状态需要花几次去消出所有的j。
我们可以预处理一个cnt[sta][i]数组表示的是在sta这个状态下去除所有的i字符需要多少次
时间复杂度是 O ( 2 k ∗ k ) O(2^k*k) O(2kk)

题目链接:

Vjudge

代码:

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
std::map<char,int> used;
const int maxm=401;
const int inf=0x7ffffff;
int dp[(1<<20)+10];
int cnt[(1<<20)+10][30],val[maxm],stk[maxm];
char s[maxm];
int n,m,tot;
inline void init(int sta)
{
	int top=0;
	for(int i=1;i<=n;i++)
	 if(!((1<<val[i])&sta)) stk[++top]=val[i];
	for(int i=1;i<=top;i++)
	 if(i==1||stk[i]!=stk[i-1]) cnt[sta][stk[i]]++;
	/*for(int i=0;i<m;i++) printf("%d ",cnt[sta][i]);
	puts("");*/
}
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%s",s);
	for(int i=1;i<=n;i++)
	{
		if(used.find(s[i-1])==used.end()) used[s[i-1]]=++tot;
		val[i]=used[s[i-1]]-1;
		//printf("%d ",val[i]);
	}
	//puts("");
	for(int i=0;i<=(1<<m)-1;i++) init(i);
	for(int i=1;i<=(1<<m)-1;i++)
	{
		dp[i]=inf;
		for(int j=0;j<m;j++)
		 if((1<<j)&i) dp[i]=std::min(dp[i],dp[i^(1<<j)]+cnt[i^(1<<j)][j]);
		//printf("%d %d\n",i,dp[i]);
	}
	printf("%d\n",dp[(1<<m)-1]);
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_200175.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?