Beyond the Void
BYVoid
USACO 4.3.1 Buy Low, Buy Lower 逢低吸納 buylow
本文正體字版由OpenCC轉換

動態規劃題,就是最長下降序列問題。第一問可以用O(N^2)的算法解決。

s[i]爲序列中第i項的值,MaxLength[i]爲以第i項爲末尾中最長下降序列長度。

狀態轉移方程爲 MaxLength[i]=max{MaxLength[j]}+1 (j=1..i-1 and s[j]>s[i])

初始條件

MaxLength[1]=1

對於第二問求最長下降序列的數量,可以通過求第一問的過程解決。設MaxCnt[i]爲第i項爲末尾中最長下降序列的個數。

對於所有的j(1≤j≤i-1)如果有(s[j]>s[i] 並且 MaxLength[j]+1>MaxLength[i])則MaxCnt[i]=MaxCnt[j],否則如果(MaxLength[j]+1==MaxLength[i])可利用加法原理,MaxCnt[i]=MaxCnt[i]+MaxCnt[j]。

考慮到題目中說的不能又重複的序列,我們可以增加一個域Next[i]表示大於i且離i最近的Next[i]使得第Next[i]個數與第i個數相同。如果不存在這樣的數則Next[i]=0。這樣我們在DP的時候如果出現Next[i]不爲0且Next[j]<i可直接跳過。

這個題數據規模很大,需要用到高精度計算,還好只是加法。 USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: buylow LANG: C++

Compiling… Compile: OK

Executing… Test 1: TEST OK [0.000 secs, 3076 KB] Test 2: TEST OK [0.011 secs, 3076 KB] Test 3: TEST OK [0.000 secs, 3076 KB] Test 4: TEST OK [0.022 secs, 3072 KB] Test 5: TEST OK [0.000 secs, 3076 KB] Test 6: TEST OK [0.011 secs, 3072 KB] Test 7: TEST OK [0.011 secs, 3076 KB] Test 8: TEST OK [0.000 secs, 3076 KB] Test 9: TEST OK [0.054 secs, 3072 KB] Test 10: TEST OK [0.324 secs, 3076 KB]

All tests OK.

Your program (‘buylow’) produced all correct answers! This is your submission #2 for this problem. Congratulations!

/*
ID: cmykrgb1
PROG: buylow
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 5002
#define MAXP 8
#define LIM 1000000000
using namespace std;


class hpnum
{
public:
	long sec[MAXP];
	int seccnt;
	
	hpnum()
	{
		sec[seccnt=1]=0;
	}
	void plus(hpnum &P)
	{
		int sect=seccnt>P.seccnt?seccnt:P.seccnt;
		long T,up=0;
		for(int i=1;i<=sect;i++)
		{
			if (i>seccnt)sec[i]=0;
			if (i>P.seccnt)P.sec[i]=0;
			T=sec[i]+P.sec[i]+up;
			up=T/LIM;
			sec[i]=T%LIM;
		}
		seccnt=sect;
		if (up)
			sec[++seccnt]=up;
	}
	void cpy(hpnum &P)
	{
		seccnt=P.seccnt;
		for (int i=1;i<=seccnt;i++)
			sec[i]=P.sec[i];
	}
};

ifstream fi("buylow.in");
ofstream fo("buylow.out");

int N;
long s[MAX],MaxLength[MAX],Next[MAX];
hpnum MaxCnt[MAX];

void init()
{
	int i,j;
	fi >> N;
	for (i=1;i<=N;i++)
		fi >>s[i];
	for (i=1;i<=N-1;i++)
		for (j=i+1;j<=N;j++)
			if (s[j]==s[i])
			{
				Next[i]=j;
				break;
			}
	s[++N]=0;
}

void dynamic()
{
	int i,j;
	MaxLength[1]=1;
	MaxCnt[1].sec[1]=1;
	for (i=2;i<=N;i++)
	{
		MaxCnt[i].sec[1]=1;
		MaxLength[i]=1;
		for (j=1;j<=i-1;j++)
		{
			if (Next[j] && Next[j]<i) continue;
			if (s[j]>s[i])
			{
				if (MaxLength[j]+1>MaxLength[i])
				{
					MaxLength[i]=MaxLength[j]+1;
					MaxCnt[i].cpy(MaxCnt[j]);
				}
				else if (MaxLength[j]+1==MaxLength[i])
				{
					MaxCnt[i].plus(MaxCnt[j]);
				}
			}
		}
	}
}

void writehp(hpnum &P)
{
	int i;
	long k;
	for (i=P.seccnt;i>=1;i--)
	{
		k=LIM/10;
		if (i!=P.seccnt && P.sec[i]<k)
		{
			//補0輸出
			while (P.sec[i]<k)
			{
				fo << 0;
				k/=10;
			}
		}
		if (P.sec[i])
			fo << P.sec[i];
	}
}

void print()
{
	fo << MaxLength[N]-1 << ' ';
	writehp(MaxCnt[N]);
	fo << endl;
	fi.close();
	fo.close();
}

int main()
{
	init();
	dynamic();
	print();
	return 0;
}

上次修改時間 2017-05-22

相關日誌