poj 1088 / 3624两道简单DP

本文主要是介绍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

题目意思很明白，求一条最长的路。这题很多方法做，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 W_i (1 ≤ W_i ≤ 400), a 'desirability' factor D_i (1 ≤ D_i ≤ 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: W_i and D_i

Output

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

Sample Input

Sample Output

题目描述都没看，看到数据就知道是个裸的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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！