HDU 2037 dp番組の手配、どのように最も多い完全な番組を視聴します

ダイナミック企画といっても、実はちょっと欲張りな思想もあります.1次元配列に保存されているのは,現在の番組を皮切りに,最大何個の異なる番組を完全に見ることができるかである.明らかに、放送時間が一番遅い番組は1しかできない.私は後ろから前への計画方法を取った.このように,iにループすると,配列中のD[i+1]->D[n-1]が最適解として保存されることが保証される.だからjをi+1からn-1にループさせ、i番目の番組を見た後で最も多く見ることができる番組数maxを見つけます.(フル視聴できるか判断するのを忘れずにね)
max+1をD[i]に保存します.このまま终わるまで.

#include <stdio.h>
#include <stdlib.h>

struct c
{
	int x;
	int y;
	int ord;
}d[100];

int cmp(const void *a, const void *b)
{
	if ((*(struct c *)a).x == (*(struct c *)b).x)
		return (*(struct c *)a).y - (*(struct c *)b).y;
	else
		return (*(struct c *)a).x - (*(struct c *)b).x;
}

int main(void)
{
	int i, j, n, max;

	while (scanf("%d", &n), n)
	{
		for (max = i = 0; i < n; i++)
		{
			scanf("%d%d", &d[i].x, &d[i].y);
			d[i].ord = 1;
		}
		qsort(d, n, sizeof(struct c), cmp);
		d[n-1].ord = 1;
		for (i = n - 2; i >= 0; i--)
		{
			for (j = i + 1; j < n; j++)
			{
				if (d[i].y <= d[j].x && d[i].ord < d[j].ord + 1)
					d[i].ord = d[j].ord + 1;
			}
			if (max < d[i].ord)
				max = d[i].ord;
		}
		printf("%d
", max);
	}

	return 0;
}