题目连接:
题目大意:
给出n个信封,这n个信封有长和宽,给出卡片的尺寸,求取能够装入卡片的最长的序列,序列满足后一个的长和宽一定大于前一个,求最长的这个序列的长度,并且给出一组可行解。
题目分析:
- 一看这种题目就是dp的题目,状态定义dp[i]为以i结尾的序列的最大的长度,并且利用一个数组记录得到最优解的路径,采取链表的形式进行存储。
- 首先对给出的信封进行排序,按照宽为第一关键字,高为第二关键字,
- 状态转移方程如下: dp[i]=maxj=0j−1{dp[j]+1},{a[j].w<a[i].w && a[j].h<a[i].h}
- 答案递归地倒序输出即可。
AC代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 5007
using namespace std;
int n,w,h;
int dp[MAX];
int back[MAX];
struct Node
{
int w,h,x;
bool operator < ( const Node & a ) const
{
if ( w == a.w ) return h < a.h;
return w < a.w;
}
}a[MAX];
void print ( int x )
{
if ( a[x]. w <= w || a[x].h <= h ) return;
print ( back[x] );
printf ( "%d " , a[x].x );
}
int main ( )
{
while ( ~scanf ( "%d%d%d" , &n , &w , &h ))
{
for ( int i = 1 ; i <= n ; i++ )
{
scanf ( "%d%d" , &a[i].w , &a[i].h );
a[i].x = i;
}
dp[0] = -1;
sort ( a+1 , a+n+1 );
for ( int i = 1 ; i <= n ; i++ )
{
int temp = -1,id = 0;
for ( int j = 0 ; j < i ; j++ )
if ( a[j].w < a[i].w && a[j].h < a[i].h && a[j].w > w && a[j].h > h )
if ( temp < dp[j] )
{
temp = dp[j];
id = j;
}
if ( a[i].w > w && a[i].h > h ) dp[i] = 1 , back[i] = 0;
else dp[i] = -1;
if ( temp+1 > dp[i] )
{
dp[i] = temp+1;
back[i] = id;
}
}
int maxn = 0;
for ( int i = 1 ; i <= n ; i++ )
maxn = max ( maxn , dp[i] );
if ( maxn == 0 )
{
puts ( "0" );
continue;
}
printf ( "%d\n" , maxn );
for ( int i = 1 ; i <= n ; i++ )
if ( maxn == dp[i] )
{
print ( i );
puts ("");
break;
}
}
}