首页 > 代码库 > 【dp】PKU 1952 buy low,buy lower
【dp】PKU 1952 buy low,buy lower
题目链接： http://poj.org/problem?id=1952
Usaco 4.3.1
Buy Low, Buy Lower
By 小兔齐齐
描述
“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:
"逢低吸纳,越低越买"
这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。
给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。
以下面这个表为例, 某几天的股价是:
天数 1 2 3 4 5 6 7 8 9 10 11 12
股价 68 69 54 64 68 64 70 67 78 62 98 87
这个例子中, 聪明的投资者(按上面的定义)，如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(可能有其他的买法):
天数 2 5 6 10
股价 69 68 64 62
格式
PROGRAM NAME: buylow
INPUT FORMAT:
(file buylow.in)
第1行: N (1 <= N <=5000), 表示能买股票的天数。
第2行以下: N个正整数 (可能分多行) ，第i个正整数表示第i天的股价. 这些正整数大小不会超过longint(pascal)/long(c++).
OUTPUT FORMAT:
(file buylow.out)
只有一行，输出两个整数：
能够买进股票的天数 长度达到这个值的股票购买方案数量
在计算方案的数量的时候，如果两个方案的股价序列相同，那么这样的两个方案被认为是相同的（只能算做一个方案）。因此，两个不同的天数序列可能产生同一个股价序列，这样只能计算一次。
SAMPLE INPUT
12
68 69 54 64 68 64 70 67
78 62 98 87
SAMPLE OUTPUT
4 2
非常漂亮的动归题目，程序里面的问题都是自己找出来的，做了3天，比较爽。这个题目说白了就是先让你求最长递减序列的长度，然后去掉重复的。这个题目关键在于去掉重复的。a[i]表示所储存的元素，然后是dp[i]表示到第i个元素的时候（包括这个元素）的最长递减序列的长度，count[i]是用来记录到第i个元素长度是dp[i]的所有结果有多少个。
现在分析去重问题。
这是这组数据的结果，dp[i]的求法就不做赘述了。然后是count[i]，如果dp[i]==1说明了，这个数必然是从1到i最大的那个，也就是count[i]=1。反之必然存在至少为2的count[i]。如果是a[j]>a[i]&&dp[j]+1==dp[i]，这个就能说明这个元素j参与了构成这个最长的下降序列，现在的问题就是如果j元素后面出现了相同的元素怎么办，当然结果就是count[i]不加这个j的count[j],因为你在前面已经加进去了。还有一个问题，如果第i号元素前面出现了，我们就直接将前面的那个元素的count赋值为0.具体的看下面的代码。
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<vector> 5 #include<set> 6 #include<queue> 7 #include<map> 8 #include<stack> 9 #include<iterator>10 #include<cstdio>11 #include<cstring>12 #include<cstdlib>13 #include<cmath>14 using namespace std;15 typedef long long ll;16 typedef unsigned long long ull;17 #define clr(c) memset(c, 0, sizeof(c));18 #define pi acos(-1.0)19 const int INF = 0x3f3f3f3f;20 const int mod = 1e9 + 7;21 const double eps = 1e-8;22 typedef struct point{23 int x, y;24 bool operator < (const point& p) const{25 if (x == p.x) return y < p.y;26 else return x < p.x;27 }28 bool operator >(const point& p) const{29 return p < *this;30 }31 }p;32 33 int n;34 int a[5005];35 int dp[5005];36 int cnt[5005];37 38 int main(){39 while(~scanf("%d", &n)){40 for(int i = 0; i < n; i++) scanf("%d", &a[i]);41 42 for(int i = 0; i < n; i++) dp[i] = 1;43 int ans = 0;44 for(int i = 0; i < n; i++){45 for(int j = 0; j < i; j++){46 if(a[i] < a[j] && dp[j]+1 > dp[i]) dp[i] = dp[j]+1;47 }48 if(ans < dp[i]) ans = dp[i];49 }50 51 for(int i = 0; i < n; i++) cnt[i] = 0;52 for(int i = 0; i < n; i++){53 for(int j = 0; j < i; j++){54 if(a[i] == a[j]) cnt[j] = 0;55 }56 if(dp[i] == 1) cnt[i] = 1;57 else{58 for(int j = 0; j < i; j++){59 if(a[i] < a[j] && dp[j]+1 == dp[i]) cnt[i] += cnt[j];60 }61 }62 }63 //for(int i = 0; i < n; i++) printf("%d ", dp[i]); printf("\n");64 //for(int i = 0; i < n; i++) printf("%d ", cnt[i]); printf("\n");65 66 int sum = 0;67 for(int i = 0; i < n; i++) if(dp[i] == ans) sum += cnt[i];68 printf("%d %d\n", ans, sum);69 }70 71 return 0;72 }
【dp】PKU 1952 buy low,buy lower