poj 1088 / 3624两道简单DP

2024-04-22 06:08
文章标签 简单 dp poj 两道 3624 1088

本文主要是介绍poj 1088 / 3624两道简单DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                                                                                        滑雪
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 90776
Accepted: 34215

Description

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
 
 1  2  3  4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

输出最长区域的长度。

Sample Input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Sample Output

25



题目意思很明白，求一条最长的路。这题很多方法做，dfs 可以，dp 也可以， 不过个人感觉还是dp效率比较高
这题卡了我一会，把二维数组变到一维的时候以为是index = (i - 1) * n + j 其实应该是 index = (i - 1) * m + j !!!!
这里的二维数组从1 1 开使到 n m结束
思路：
因为这个图的高度没啥顺序关系，你只能确定某一点能不能往周围走，不能确定某一点往哪边走能走的最远，所以得把所有点从小到大排序，然后从顺序小的点开始，刷新周围比他高的点的路径，所以需要dp数组记下坐标，高度(排序时用)，最大长度。。。从小到大刷新，则最后高度高的点的路程一定是最长的。。
 
/** poj.cpp**  Created on: 2016年7月20日*      Author: triose*///#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<iterator>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<map>
#include<set>
using namespace std;
//#define ONLINE_JUDGE
#define eps 1e-8
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define enter putchar(10)
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define repe(i,a,b) for(int i = (a); i <= (b); ++i)
#define mem(a,b) (memset((a),b,sizeof(a)))
#define sf(a) scanf("%d",&a)
#define sfI(a) scanf("%I64d",&a)
#define sfd(a,b) scanf("%d%d",&a,&b)
#define sft(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sfs(a) scanf("%s",a)
#define pf(a) printf("%d\n",a)
#define pfd(a,b) printf("%d %d\n",a,b)
#define pfP(a) printf("%d %d\n",a.fi,a.se)
#define pfs(a) printf("%s\n",a)
#define pfI(a) printf("%I64d\n",a)
#define PR(a,b) pair<a,b>
#define fi first
#define se second
#define LL long long
#define DB double
const double PI = acos(-1.0);
const double E = exp(1.0);
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> inline T Min(T a, T b) { return a < b ? a : b; }
template<class T> inline T Max(T a, T b) { return a > b ? a : b; }
int n, m;
#define N 110
#define M 10010
int a[N][N];
struct Node {int x, y;int high;int len;friend bool operator < (const Node & a, const Node & b) {return a.high < b.high;}
};
Node dp[M];
int max_len;
void check() {repe(i, 1, n * m) {printf("%d%c", dp[i].len, (i % m == 0 ? '\n' : ' '));}
}
void flash(int pos) {int x = dp[pos].x;int y = dp[pos].y;int flag1 = (x - 1) * m + y;rep(i, -1, 2) {rep(j, -1, 2) {int tmpx = x + i; int tmpy = y + j;if(i == j || i == -j) continue;if(tmpx > n || tmpx < 1 || tmpy < 1 || tmpy > m) continue;int flag2 = (tmpx - 1) * m + tmpy;if(a[tmpx][tmpy] > a[x][y]) {dp[flag2].len = Max(dp[flag2].len, dp[flag1].len + 1);max_len = Max(dp[flag2].len, max_len);}}}
}
int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
//	freopen("Out.txt", "w", stdout);
#endifwhile(~sfd(n, m)) {max_len = 1;repe(i, 1, n) {repe(j, 1, m) {sf(a[i][j]);int tmp = (i - 1) * m + j;dp[tmp].x = i; dp[tmp].y = j;dp[tmp].high = a[i][j];dp[tmp].len = 1;}}int cnt = n * m;sort(dp + 1, dp + cnt + 1);repe(i, 1, cnt) flash(i);pf(max_len);
//		check();}return 0;
}




Charm Bracelet
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 33137 Accepted: 14690

Description

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di

Output

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

Sample Input

4 6
1 4
2 6
3 12
2 7

Sample Output

23

题目描述都没看，看到数据就知道是个裸的01背包。。秒秒钟敲出来发现既然TLE（百练上超时，POJ  MLE）！！！十分不解。。
先贴超内存代码： 
/** poj.cpp**  Created on: 2016年7月20日*      Author: triose*///#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<iterator>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<map>
#include<set>
using namespace std;
//#define ONLINE_JUDGE
#define eps 1e-8
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define enter putchar(10)
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define repe(i,a,b) for(int i = (a); i <= (b); ++i)
#define mem(a,b) (memset((a),b,sizeof(a)))
#define sf(a) scanf("%d",&a)
#define sfI(a) scanf("%I64d",&a)
#define sfd(a,b) scanf("%d%d",&a,&b)
#define sft(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sfs(a) scanf("%s",a)
#define pf(a) printf("%d\n",a)
#define pfd(a,b) printf("%d %d\n",a,b)
#define pfP(a) printf("%d %d\n",a.fi,a.se)
#define pfs(a) printf("%s\n",a)
#define pfI(a) printf("%I64d\n",a)
#define PR(a,b) pair<a,b>
#define fi first
#define se second
#define LL long long
#define DB double
const double PI = acos(-1.0);
const double E = exp(1.0);
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> inline T Min(T a, T b) { return a < b ? a : b; }
template<class T> inline T Max(T a, T b) { return a > b ? a : b; }
int n, m;
#define N 3500
#define M 13000
int dp[N][M];
int v[N], w[N];
int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
//	freopen("Out.txt", "w", stdout);
#endifwhile(~sfd(n, m)) {repe(i, 1, n) sfd(w[i], v[i]);mem(dp, 0);repe(i, 1, n) {for(int j = 1; j <= m; j++) {if(j >= w[i])dp[i][j] = Max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);else dp[i][j] = dp[i - 1][j];}}pf(dp[n][m]);}return 0;
}


01背包原理就不说了，都被讲烂了
接下来看怎么优化。
核心的代码在这： 
if(j >= w[i])dp[i][j] = Max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
else dp[i][j] = dp[i - 1][j];
可见：dp[i][j]的值在dp数组上只与dp[i][k] (k <= j)的值有关系。如果上一行某个状态dp[i - 1][k]满足条件，则等于这个状态加第i个物品的价值。如果不满足条件，则就等于上一行的当前状态dp[i - 1][j]。
那么第 [i, i - 2]区间里的值对确定当前状态是无用的，那为什么要保存他们？
所以采用滚动数组的方式： 
repe(i, 1, n) {for(int j = m; j >= w[i]; j--) {dp[j] = Max(dp[j - w[i]] + v[i], dp[j]);}
}
为什么能这样？因为和上面那段代码等效。j的循环会选择性执行这一句，dp[j] = Max(dp[j], dp[j - w[i]] + v[i])
而没被选择到的（j < w[i]）的dp[j] 还是等于自身。从而通过这种方法降低了数组的维度。节省了时间和空间。 

/** poj.cpp**  Created on: 2016年7月20日*      Author: triose*///#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<iterator>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<map>
#include<set>
using namespace std;
//#define ONLINE_JUDGE
#define eps 1e-8
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define enter putchar(10)
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define repe(i,a,b) for(int i = (a); i <= (b); ++i)
#define mem(a,b) (memset((a),b,sizeof(a)))
#define sf(a) scanf("%d",&a)
#define sfI(a) scanf("%I64d",&a)
#define sfd(a,b) scanf("%d%d",&a,&b)
#define sft(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sfs(a) scanf("%s",a)
#define pf(a) printf("%d\n",a)
#define pfd(a,b) printf("%d %d\n",a,b)
#define pfP(a) printf("%d %d\n",a.fi,a.se)
#define pfs(a) printf("%s\n",a)
#define pfI(a) printf("%I64d\n",a)
#define PR(a,b) pair<a,b>
#define fi first
#define se second
#define LL long long
#define DB double
const double PI = acos(-1.0);
const double E = exp(1.0);
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> inline T Min(T a, T b) { return a < b ? a : b; }
template<class T> inline T Max(T a, T b) { return a > b ? a : b; }
int n, m;
#define N 3500
#define M 13000
int v[N], w[N];
int dp[M];
int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
//	freopen("Out.txt", "w", stdout);
#endifwhile(~sfd(n, m)) {repe(i, 1, n) sfd(w[i], v[i]);mem(dp, 0);repe(i, 1, n) {for(int j = m; j >= w[i]; j--) {dp[j] = Max(dp[j - w[i]] + v[i], dp[j]);}}pf(dp[m]);}return 0;
}


这篇关于poj 1088 / 3624两道简单DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/924973。

相关文章

使用Python开发一个简单的本地图片服务器

使用Python开发一个简单的本地图片服务器

《使用Python开发一个简单的本地图片服务器》本文介绍了如何结合wxPython构建的图形用户界面GUI和Python内建的Web服务器功能,在本地网络中搭建一个私人的,即开即用的网页相册,文中的示... 目录项目目标核心技术栈代码深度解析完整代码工作流程主要功能与优势潜在改进与思考运行结果总结你是否曾经
阅读更多...
Mysql表的简单操作(基本技能)

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例：修改表在数据库中，表的操作主要
阅读更多...
springboot简单集成Security配置的教程

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》：本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig（自定义资源权限规则
阅读更多...
如何使用Python实现一个简单的window任务管理器

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i
阅读更多...
C++中函数模板与类模板的简单使用及区别介绍

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中，模板是实现泛型编程
阅读更多...
使用EasyExcel实现简单的Excel表格解析操作

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》：本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis
阅读更多...
Java中数组转换为列表的两种实现方式(超简单)

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架（Arrays.asList）1.1 示例代码1.
阅读更多...
Java8需要知道的4个函数式接口简单教程

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》：本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口？Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
redis群集简单部署过程

redis群集简单部署过程

《redis群集简单部署过程》文章介绍了Redis,一个高性能的键值存储系统,其支持多种数据结构和命令,它还讨论了Redis的服务器端架构、数据存储和获取、协议和命令、高可用性方案、缓存机制以及监控和... 目录Redis介绍1. 基本概念2. 服务器端3. 存储和获取数据4. 协议和命令5. 高可用性6.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2