简单区间dp(nyoj 746 && poj 2955)_汤匙的匙不是钥匙的匙的博客-程序员宝宝

技术标签: NYOJ  POJ  动态规划  

下面是在别的地方看到的(虽然不知道准不准确先转再说……):

区间动态规划问题一般都是考虑,对于每段区间,他们的最优值都是由几段更小区间的最优值得到,是分治思想的一种应用,将一个区间问题不断划分为更小的区间直至一个元素组成的区间,枚举他们的组合 ,求合并后的最优值。

设F[i,j](1<=i<=j<=n)表示区间[i,j]内的数字相加的最小代价
最小区间F[i,i]=0(一个数字无法合并,∴代价为0)

每次用变量k(i<=k<=j-1)将区间分为[i,k]和[k+1,j]两段

For p:=1 to n do // p是区间长度,作为阶段。 
for i:=1 to n do // i是穷举的区间的起点
begin
j:=i+p-1; // j是 区间的终点,这样所有的区间就穷举完毕
if j>n then break; // 这个if很关键。
for k:= i to j-1 do // 状态转移,去推出 f[i,j]
f[i , j]= max{f[ i,k]+ f[k+1,j]+ w[i,j] } 
end; 
这个结构必须记好,这是区间动态规划的代码结构。

nyoj 746:点击打开链接

状态转移方程:dp[i][j] = max(dp[i][j], dp[k][j - 1] * num[k + 1][i]) 定义dp[i][j]为将下标到i为止的数字串分成j个部分后乘积的最大值。

k是起点和终点之间的一个分割点, dp[k][j - 1]是将前面下标到k为止的数字串分成j - 1个部分所得的乘积的最大值, 为什么是j  - 1呢,因为k就是一个分割点。num[k + 1][i]是k + 1位置到i位置的对应数的乘积。

通过枚举分割点的位置找到乘积的最大值。

#include <stdio.h>
#include <string.h>
#define MAX 10000000
int m;
char n[25];
long long num[25][25];
long long dp[25][25];

void change()
{//将每一段对应的数字存储到num数组中
	int i, j, len = strlen(n);
	int k = 0;
	for(i = 0; i < len; i++)
	{
		k = 0;
		for(j = i; j < len; j++)
		{
			k = k * 10 + (n[j] - 48);
			num[i][j] = k;
		}
	}
}

long long max(long long a, long long b)
{
	return a > b ? a : b;
}

int main (void)
{
	int t;	
	scanf("%d", &t);
	while(t --)
	{
		memset(dp, 0, sizeof(dp));
		scanf("%s %d", n, &m);
		change();
		int i, j, k, len = strlen(n);
		for(i = 0; i < len; i++)
		//将0-i位置的数分成1份所得的最大值就是这个数本身 
			dp[i][1] = num[0][i];
		
		for(i = 0; i < len; i++)
		{//当前划分的长度为i 
			for(j = 1; j <= m; j++)
			{//划分成j个部分 
				for(k = 0; k <= i; k++)//划分的位置 
					dp[i][j] = max(dp[i][j], dp[k][j - 1] * num[k + 1][i]);
			}
		}
		printf("%lld\n", dp[len - 1][m]);
	}
	return 0;
}


poj 2955:点击打开链接

dp[i][j]表示起点为i终点为j的匹配的括号数的最大值。

#include <stdio.h>
#include <string.h>
 
char s[110];
int dp[110][110];

int yes(char a, char b)
{
	if(a == '(' && b == ')')
		return 1;
	if(a == '[' && b == ']')
		return 1;
	return 0;
}

int max (int a, int b)
{
	return a > b ? a : b;
}

int main (void)
{
	while(scanf("%s", s) != EOF)
	{ 
		if(s[0] == 'e')
			break;
		int len = strlen(s);
		memset(dp, 0, sizeof(dp));
		int i, j, k, p;
		for(i = 0; i < len - 1; i++)
			if(yes(s[i], s[i + 1]))
				dp[i][i + 1] = 2;//如果 
				
		for(p = 3; p <= len; p++)
		{//p是字符串的长度,因为上面已经配对过相邻两个括号所以p从3开始 
			for(i = 0; i < len; i++)
			{//i是起点 
				j = i + p - 1;//j为终点 
				if(j >= len)
					break;
				if(yes(s[i], s[j]))//如果匹配 
					dp[i][j] = dp[i + 1][j - 1] + 2;
			//2是已经匹配的i位置和j位置的两个括号,再加上剩下的i+1位置到j-1位置字串的最大匹配数 
				for(k = i; k < j; k++)//k是分割点 
					dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
					//i位置到k位置的匹配最大值加上k+1位置到j位置匹配的最大值 
			}
		}
		printf("%d\n", dp[0][len - 1]);
	}
	return 0;
}


Problem 111: 单词的划分


Time Limit:1 Ms|  Memory Limit:64 MB
Difficulty:2

Description

有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析,需要将它划分成若干个部分,每个部分称为一个单词。出于减少分析量的目的,我们希望划分出的单词数越少越好。你就是来完成这一划分工作的

Input

第一行,一个字符串。(字符串的长度不超过100)
第二行一个整数n,表示单词的个数。(n<=100)
第3~n+2行,每行列出一个单词。

Output

一个整数,表示字符串可以被划分成的最少的单词数。

Sample Input

realityour
5
real
reality
it
your
our

Sample Output

2

Hint

原字符串可拆成real+it+your或reality+our,由于reality+our仅为两个部分,因此最优解为2,另外注意,单词列表中的每个单词都可以重复使用多次,也可以不用

这个也是个区间动归题。

dp[i]为长度是i的单词所划分的最小单词数。

#include <stdio.h>
#include <string.h>

char s[110];
int n;
char word[110][50];
int dp[110];

int same(int x, int y)
{//从后向前比较 
	int i, j, l = strlen(word[y]);
	for(i = 0; i < l; i++)
	{
		if(s[x - i] != word[y][l - 1 - i])
			return 0;
	}
	return 1;
}

void init()
{
	int i, j;
	for(i = 0; i < 110; i++)
		dp[i] = 10000000;
}

int min (int a, int b)
{
	return a < b ? a : b;	
}

int main (void)
{
	while(scanf("%s", &s[1]) != EOF)
	{
		scanf("%d", &n);
		int i, j;
		for(i = 0; i < n; i++)
			scanf("%s", word[i]);
		int len = strlen(&s[1]);
		init();
		dp[0] = 0;
		for(i = 1; i <= len; i++)
		{//i是长度。注意i要从1开始,不然下面dp[i - 1]会出错 
			for(j = 0; j < n; j++)
			{//j遍历所给的单词 
				int l = strlen(word[j]);
				if(i < l - 1)
					continue;
				if(same(i, j))
				{//如果能分成某个单词,就选择最小的 
					dp[i] = min(dp[i], dp[i - l] + 1);
				}
			}
		}
		/*
		for(i = 0; i <= len; i++)
			printf("%d  ", dp[i]);
		printf("\n");
		*/
		printf("%d\n", dp[len]);
	}
	return 0;
}


参考:点击打开链接


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u013207805/article/details/24436591

智能推荐

immutable.js常用方法_如沐春风xsy的博客-程序员宝宝_immutable.js

immutable.js常用方法fromJS():把js数据转为immutable数据(深转换)//const obj = fromJS({name:'Tom',age:18})/const list = fromJS([1,2,3])toJS():把immutable数据转为js数据(深转换)//const obj1 = obj.toJS()/const list1 = list.toJS()Map():把object转为immutable数据(浅转换)//const obj2 = Map({

android新建model,android中模块间共享ViewModel实例_xander Sun的博客-程序员宝宝

我正在研究MVVM架构。我想在我的android应用程序的模块之间共享一个视图模型实例。当用户从应用程序模块完成骑行时,我想访问我的聊天模块视图模型实例来执行一些数据库操作,例如清除对话实体等。我正在使用带有视图模型的房间数据库。ChatActivityNew是聊天模块中的一个活动。应用程序模块预订活动Dialogs.INSTANCE.showRideStatusDialog(mCurrentAc...

尚硅谷的javaweb servlet的代码时候 实例化Servlet类[com.servlet.ParameterServlet]异常_丢掉幻想,准备斗争的博客-程序员宝宝

在写尚硅谷的javaweb servlet的代码时候 发生实例化Servlet类[com.servlet.ParameterServlet]异常解决办法apache-tomcat版本问题原来发生错误:apache-tomcat-10.0.5现在:apache-tomcat-9.0.45

POJ 2955(区间dp)_superFool_song的博客-程序员宝宝

//简单区间DP//题意: 给你一串括号 问你最多有几个可以匹配// dp[i][j]表示从i到j 最多可以匹配的括号数// dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2)(str[i]与str[k]可以匹配)#include#include#define N 110#define max(a,b) a>

判断一个域名是否合法_dengshouzi7943的博客-程序员宝宝

生活中我们肯定会见到很多域名(domain name,简称domain)。域名有很多形式,以句点(.)作为分隔符。这里说的域名是纯域名,不是网址,不包括http://(或https://),也不带斜线。常见的域名形式1. 由两个部分组成,例如baidu.com(百度),csdn.net(CSDN),wikipedia.org(维基百科)。2. 由多个部分组成...

随便推点

【JS】Math 对象用法_一颗不甘坠落的流星的博客-程序员宝宝

文章目录Math 对象一、Math 对象属性二、min()和max()方法三、舍入方法ceil()、floor()、round()、fround()四、random()方法五、其它方法Math 对象扩展:Math 对象上提供的计算要比直接在JavaScript实现的快的多,因为Math 对象上的计算使用了 JavaScript引擎中更高效的实现和处理器指令。但使用 Math 计算的问题是精度因浏览器、操作系统、指令集和硬件而异。一、Math 对象属性Math 对象有一些属性,主要用于保存数学中

EMGU.CV入门(十五、模板匹配)_LyRics1996的博客-程序员宝宝_emgucv 模板匹配

一、函数介绍1.1 MatchTemplate模板匹配函数参数说明参数1:输入图像参数2:匹配模板参数3:返回矩阵参数4:算法类型其中算法类型共计六种: // // 摘要: // This function is similiar to cvCalcBackProjectPatch. It slids through image, // compares overlapped patches of size

Thinkphp5第十七讲:路由之路由注册_sky根的博客-程序员宝宝

本节主要讲解TP5的路由模式以及注册路由规则,本人在项目开发时一般都使用默认模式,如有特殊需求可以自定义路由模式,本节不需要刻意去记,作为工具可以随时翻看,会用即可。一、路由模式1、普通模式。关闭路由完全使用默认的PATH_INFO方式,即http://server/module/controller/action/param/value/......在config.php中设置,...

solidworks怎样增加视图方向,并用在工程图上_TIM邓肯的博客-程序员宝宝

在屏幕上单击鼠标右键,通过“旋转视图”(图中红色箭头所指)、“翻滚视图”(图中蓝色箭头所指)等命令,将视图调整至我们需要的方向也可以通过“Alt+→”、“Alt+←”、“Shift+↑”、“Shift+↓”等快捷键来实现视图方向的改变调好视图方向后,按键盘上的空格键,出现“方向”对话框,点击“新视图”(图中红色箭头所指)...

Django实现页面注册登录界面_码源的博客-程序员宝宝_django注册登录页面

增加数据在acsign/models.py中增加用户数据:class Users(models.Model): u_name = models.CharField(max_length=10) u_password = models.CharField(max_length=255) u_ticket = models.CharField(max_length=30, ...

Ubuntu学习之Linux软件的安装_WflytoC的博客-程序员宝宝_linuxcnc百科

通过源码安装软件1.什么是源码包附带有程序的源代码、configure文件、说明文档的安装包一般先以tar打包,再以压缩软件压缩,如tar.gz或tar.bz2文件需要自定义参数进行编译安装2.configure自定义参数配置安装环境,必要性检查生成makefile文件3.make & install编译生成二进制文件执行安装4.使用源码包进行安装的过程获取源码安装包,可以去官

推荐文章

热门文章

相关标签