放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

POJ 1065 Wooden Sticks 题解 《挑战程序设计竞赛(第2版)》

POJ 1065 Wooden Sticks

n根木材长l_i重w_i,前一根木材大于后一根的话要浪费一分钟准备机器,求最省方案?

关键字:最长下降子序列 LDS 鸽笼原理

2.3 记录结果再利用的“动态规划” 需稍加思考的题目

题目的确需要稍加思考,这道题的要求其实是将所有stick分为x个不下降子序列( Ai <= Ai+1 ),然后问题归结于求x的最小值。

x的最小值其实等于按l递增排序后stick按w最长下降子序列的长度L,证明如下:

若x < L,先从stick中取出最长下降子序列L,取走的元素留下一个大小相同的“空穴”,然后将剩下的元素和空穴分成x个不下降子序列。接着把最长下降子序列L中的L个元素放回这L个空穴里。由于x < L,所以根据鸽笼原理,必然有两个或两个以上的下降子序列L中的元素(b > a)被按顺序放到同一个不下降子序列(a <= b),产生矛盾(两者本应该是等效的)。

问题归结于求解最长下降子序列的长度L,定义:

dp[i] := 长度为i+1的下降子序列中末尾元素的最大值,两重遍历,复杂度为O(n2)

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

pair<int, int> stick[5000 + 16];
int dp[5000 + 16];				// dp[i] := 长度为i+1的下降子序列中末尾元素的最大值

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		for (int i = 0; i < n; ++i)
		{
			cin >> stick[i].first >> stick[i].second;
		}
		sort(stick, stick + n);
		memset(dp, -1, n * sizeof(int));
		for (int j = 0; j < n; ++j)
		{
			for (int i = 0; i < n; ++i)
			{

				if (i == 0 || dp[i - 1] > stick[j].second)
				{
					dp[i] = max(dp[i], stick[j].second);
				}
			}
		}
		cout << lower_bound(dp, dp + n, -1, greater<int>()) - dp << endl;
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

12509937 hankcs 1065 Accepted 276K 94MS C++ 1054B 2014-02-10 18:09:54

这样不够快,因为dp是一个递减的序列,对于每个元素最多只需一次更新。至于哪个位置需要更新,可以利用二分搜索将复杂度降低到O(nlogn):

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

pair<int, int> stick[5000 + 16];
int dp[5000 + 16];				// dp[i] := 长度为i+1的下降子序列中末尾元素的最大值

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		for (int i = 0; i < n; ++i)
		{
			cin >> stick[i].first >> stick[i].second;
		}
		sort(stick, stick + n);
		memset(dp, -1, n * sizeof(int));
		for (int i = 0; i < n; ++i)
		{
			*lower_bound(dp, dp + n, stick[i].second, greater<int>()) = stick[i].second;
		}
		cout << lower_bound(dp, dp + n, -1, greater<int>()) - dp << endl;
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

12509948 hankcs 1065 Accepted 280K 47MS C++ 984B 2014-02-10 18:12:29

于是就快了一倍。


知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 1065 Wooden Sticks 题解 《挑战程序设计竞赛(第2版)》

分享到:更多 ()

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机