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。

相关文章

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu2289（简单二分）

hdu2289（简单二分）

虽说是简单二分，但是我还是wa死了  题意：已知圆台的体积，求高度 首先要知道圆台体积怎么求：设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ
阅读更多...
hdu4826（三维DP）

hdu4826（三维DP）

这是一个百度之星的资格赛第四题 题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意：从左上角的点到右上角的点，每个点只能走一遍，走的方向有三个：向上，向下，向右，求最大值。 咋一看像搜索题，先暴搜，TLE,然后剪枝，还是TLE.然后我就改方法，用DP来做，这题和普通dp相比，多个个向上
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
hdu4865(概率DP)

hdu4865(概率DP)

题意：已知前一天和今天的天气概率，某天的天气概率和叶子的潮湿程度的概率，n天叶子的湿度，求n天最有可能的天气情况。 思路：概率DP，dp[i][j]表示第i天天气为j的概率，状态转移如下：dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下： #include <stdio.h>#include
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
usaco 1.1 Broken Necklace（DP）

usaco 1.1 Broken Necklace（DP）

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于： 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
poj 1511 Invitation Cards(spfa最短路)

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离，求来回到点1的最短路中的边权和。 因为边很大，不能用原来的dijkstra什么的，所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码： #include<stdio.h>#include<stack>using namespace std;const int M
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2