/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://poj.org/problem?id=1952
Name : 1952 BUY LOW, BUY LOWER
Date : Tuesday, July 10, 2012
Time Stage : 2 hours
Result:
0411693 panyanyany
1952
Accepted 224K 172MS C++
1970B 2012-07-10 09:44:02
Test Data :
Review :
参考:
http://blog.acmj1991.com/?p=606
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
using namespace std ;
#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define INF (0x3f3f3f3f)
#define MAXN (5005)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)|1)
#define M(x, y) (((x)+(y)) >> 1)
#define DB //
int sum, a[MAXN], dp[MAXN], route[MAXN];
int LIS(int a[], int n)
{
int i, j;
for (i = 0; i < n; ++i)
{
dp[i] = 1;
route[i] = 1;
for (j = 0; j < i; ++j)
{
if (a[j] > a[i])
{
if (dp[j] + 1 > dp[i])
{
route[i] = route[j];
dp[i] = dp[j] + 1;
}
else if (dp[j] + 1 == dp[i])
{
route[i] += route[j];
}
}
}
// 去重,比如 5 2 3 2,当 i==3时,计算到第2个2,那么对于以后的数来
// 说,第1个2的route就是多余的了。因为凡是比2小的数,比如1,显然跟第2个2
// 比较更好,因为(dp[3] = 3) > (dp[1] = 2)。然后再普及到一般的情况:
// 5 2 1 2, 此时两个2的route和dp都一样,所以第一个2多余.
for (j = 0; j < i; ++j)
if (a[i] == a[j])
route[j] = 0;
}
j = 0;
for (i = 0; i < n; ++i)
{
if (dp[j] < dp[i])
j = i;
}
for (i = 0; i < n; ++i)
if (i != j && dp[j] == dp[i])
route[j] += route[i];
return j;
}
int main()
{
int i, j, n;
while (scanf("%d", &n) != EOF)
{
for (i = 0; i < n; ++i)
scanf("%d", a+i);
j = LIS(a, n);
printf("%d ", dp[j]);
printf("%d\n", route[j]);
}
return 0;
}
分享到:
相关推荐
北大POJ经典结题报告 北大POJ经典结题报告 北大POJ经典结题报告 注重方法,内容详尽,物超所值
很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...
如果你为在poj上找不到解题思路而痛苦,那么这本书可以为你带来惊喜,里面包括了poj上一部分题解题报告~
ACM POJ 解题报告北大POJ 大量解题代码
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大POJ1837-Balance
北大POJ1159-Palindrome
北大poj JAVA源码
北大POJ第1324题(C++)
北大POJ第1005题答案(C语言)
北大POJ200多道程序解答 完整代码 供大家参考 相互切磋
北大POJ1163-The Triangle
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习
北大POJ1080-Human Gene Functions
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
北大POJ初级-动态规划 解题报告+AC代码
把北京大学的题库编译好,可以离线看的chm文件,我觉得是好东西
北大POJ初级-简单搜索 解题报告+AC代码
此压缩包包含北京大学POJ题目的绝大部分解题代码,一道题目有不同语言的编程,但主要是C++语言,仅供大家学习之用。