9.2.2(직사각형 중첩 단순 동적 계획)

어지러워 죽겠어. 드디어 내가 뭘 잘못했는지 찾았어.
다른 사람이 표시하는 dp 구법은 기억화 검색입니다. 당신의 그 기억화는 비록 있지만, 당신은 결과를 한꺼번에 잘 사용하지 않았습니다.
즉 당신은 dp 한 번도 결과를 저장하지 않고,
코드를 보십시오:
#include 
#include 
#include 
#include 

#define max(a, b) (a) > (b) ? (a) : (b)

using namespace std;

struct node{
	int a;
	int b;
}q[1005];

int n;

int map[1005][1005];

int d[1005];

bool Judge(int i, int j)
{
	if (q[i].a < q[j].a && q[i].b < q[j].b || q[i].a < q[j]. b && q[i].b < q[j].a)
	{
		return true;
	}
	return false;
}

int dp(int i)
{
	//     ans       d[i]   ,                 ,,,ans           
	 
	int &ans = d[i]; //            ,   TLE  TLE   ,        ,     ,      , 
	if (ans > 0)  //           ,           d[i];            , 
	{
		return  ans;
	}
	ans = 1;
	for (int j = 0; j < n; j++)
	{
		if (map[j][i])
		{
			ans = max(ans, dp(j) + 1);
		}
	}   
	return ans;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		memset(map, 0, sizeof(map));
		scanf("%d", &n);
//		if (n == 0)
//		{
//			printf("-1
"); // continue; // } for (int i = 0; i < n; i++) { scanf("%d%d",&q[i].a, &q[i].b); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (Judge(i, j)) { // cout << "i = " << i << " " << "j = " << j << endl; map[i][j] = 1; } } } int t = 0; memset(d, 0, sizeof(d)); for (int i = 0; i < n; i++) { d[i] = dp(i); // printf("dp[%ds] = %d", i + 1, d[i]); // cout << endl; t = max(t, d[i]); } printf("%d
", t); } // system("pause"); return 0; }

사전순으로 출력할 수 있도록 수정하십시오.
당신의 직사각형 번호:
#include 
#include 
#include 
#include 

#define max(a, b) (a) > (b) ? (a) : (b)

using namespace std;

struct node{
	int a;
	int b;
}q[1005];

int n;

int cnt;

int map[1005][1005];

int d[1005];

int seq[1005];

bool Judge(int i, int j)
{
	if (q[i].a < q[j].a && q[i].b < q[j].b || q[i].a < q[j]. b && q[i].b < q[j].a)
	{
		return true;
	}
	return false;
}

void print_ans(int i)
{
//	printf("%d ", i + 1);
	for (int j = 0; j < n; j++)
	{
		if (map[j][i] == 1 && d[i] == d[j] + 1)
		{
			seq[cnt++] = j + 1;
			print_ans(j);
			break;
		}
	}
} 

int dp(int i)
{
	//     ans       d[i]   ,                 ,,,ans           
	 
	int &ans = d[i]; //            ,   TLE  TLE   ,        ,     ,      , 
	if (ans > 0)  //           ,           d[i];            , 
	{
		return  ans;
	}
	ans = 1;
	for (int j = 0; j < n; j++)
	{
		if (map[j][i])
		{
			ans = max(ans, dp(j) + 1);
		}
	}   
	return ans;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		memset(map, 0, sizeof(map));
		scanf("%d", &n);
//		if (n == 0)
//		{
//			printf("-1
"); // continue; // } for (int i = 0; i < n; i++) { scanf("%d%d",&q[i].a, &q[i].b); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (Judge(i, j)) { // cout << "i = " << i << " " << "j = " << j << endl; map[i][j] = 1; } } } int t = 0; int flag; memset(d, 0, sizeof(d)); int i; for (i = 0; i < n; i++) { d[i] = dp(i); // printf("dp[%ds] = %d", i + 1, d[i]); // cout << endl; // t = max(t, d[i]); if (t < d[i]) { t = d[i]; flag = i; } } cnt = 0; seq[cnt++] = flag + 1; print_ans(flag); for (int j = cnt - 1; j >= 0; j--) { printf("%d ", seq[j]); } printf("
"); printf("%d
", t); } system("pause"); return 0; }

좋은 웹페이지 즐겨찾기