NOIP 1999迎撃ミサイル

これは1本のとても経典のダイナミックな计画の问题で、私のこのようなまだシステム学のアルゴリズムの人に対して、やはり多くの练习を加えなければならなくて、多くの人はこの问题の解题の报告を书いたことがあって、私はやはり自分で1篇を书くことを决めて、自分で理解を深めることを助けて、DPに対してどんな感じがないと感じて、问题の考え方を手に入れてこれは私にとって問題です.
タイトルリンク:http://www.rqnoj.cn/Problem_217.html
RQNOJは高校NOIP選手が作ったOJだそうです.多くの高校NOIP競技選手に使われています.
長い間考えていたが、他の人にヒントを与えられて動的回転方程式を見つけた.
a[k]を最後尾とする最長不増子シーケンスを考え,一つの状態としてn個(最後尾はa[n−1])を合計し,n+1の場合,末尾がa[n]よりも小さく,最長不増子シーケンスであればよいと考え,一度計算すると最長子シーケンスの値,すなわち最初の質問の対象が得られ,第2の質問については,もう一度考慮する必要がある.私たちは元のシーケンスで見つかった最長男シーケンスを削除して、最も長いシーケンスを探し続けたいと思っていますが、最長男シーケンスには多くの選択肢がある場合、どうすればいいのでしょうか.たとえば、次のような場合があります.
8
1 16 3 6 18 9 14 12
最初のステップは長男シーケンスを探します:16 14 12、または18 14 12
まず、このような葛藤の問題はサブシーケンスのトップにしか現れません.(なぜか自分で考えます)、このとき、この2つのシーケンスを取り除くべきですか.
最初の数字の後ろの合計が前のものより大きいことがわかります.(18>16)、(例えば18を15に変更します.そうしないと、前の数を1番目にして、後ろのすべてのサブシーケンスを加えて、より長いサブシーケンスを得ることができます.(16 15 14 12)
次の最初の数字がもっと大きいことを知っています
このとき、私たちは小さい最初の数字を取るべきです.16を取ると、18を取ると、18の後ろに16と増分しないサブシーケンスを構成できない数字があるかもしれません.16のように、18を残すと、16を取るとこの問題はありません.18の後にあるサブシーケンスに割り込むことができれば、今でもいいですが、16 18の間の数は18より小さいに違いありません.(そうでなければ、以上の議論はありません.後者のサブシーケンスは長さを1に変更することができます)だから、彼らはもともとある18の冒頭のサブシーケンスに割り込むことができませんでしたが、今はまだできません.だから、私たちは前のものを取るほうが次のステップで長男シーケンスを取るのに有利だと結論しました.だから、一番前のものを取ります.
コードは次のとおりです.

#include
#include
#include
#include
using namespace std;
struct re
{
		int len, ak, res[1000];
};

int count(int *a, re *b, int n, int *m)
{
		int max = 1, maxi = 1, i, j, k;

		b[0].ak = a[0];
		b[0].len = 1;
		b[0].res[0] = a[0];
		for (i = 1; i < n; ++i)
		{
				b[i].ak = a[i];
				b[i].len = 1;
				b[i].res[0] = a[i];
				for (j = 0; j < i; ++j)
				{
						if (b[j].ak >= b[i].ak)
						{
								if (b[i].len < b[j].len + 1)
								{
										b[i].len = b[j].len + 1;		
										for (k = 0; k < b[j].len; ++k)
												b[i].res[k] = b[j].res[k];
										b[i].res[b[j].len] = a[i];
								}
						}
				}
		}
		for (i = 0; i < n; ++i)
		{
				if (b[i].len > max)
				{
						max = b[i].len;
						maxi = i;
				}
		}
		*m = maxi;

		return max;
}

int main()
{
		int i, j, k, n, *a = NULL, *c = NULL, max, maxi, num;		
		re *b = NULL;

		while (cin >> n)
		{
				i = 0;
				max = -1;
				maxi = -1;
				num = 1;
				a = (int *) malloc (n * sizeof(int));
				c = (int *) malloc (n * sizeof(int));
				b = (re *) malloc (n * sizeof(re));
				memset(b, 0, sizeof(b[0]) * n);
				while (i < n)
						cin >> a[i++];		
				max = count(a, b, n, &maxi);					
				cout << max << ' ';
				while (max != n)
				{
						for (i = 0, j = 0, k = 0; i < n; ++i)
						{
								if (a[i] == b[maxi].res[j])
										j++;
								else
										c[k++] = a[i];
						}
						n = n - max;
						for (i = 0; i < n; ++i)
								a[i] = c[i];
						memset(b, 0, sizeof(b[0]) * n);
						max = count(a, b, n, &maxi); 
						num++;
				}
				cout << num << endl;
		}

		return 0;
}

いくつかの説明:
長男の序列を絶えず取り除き、残りの序列の中で長男の序列を探し続けると、第2の質問を解決することができ、貪欲な思想に似ている.
構造体b[i]は、a[0]からa[i]までの最上位シーケンスの長さlen、最上位シーケンスの最後の数値ak、およびこのシーケンスres[1000]を保存する.