题目:矩形嵌套
import java.util.Scanner; public class Main {//深搜超时---TimeLimitExceeded -- -- java 2013-07-23 22:55:29 static F f[]; static int n,max; public static void main(String[] args) { Scanner input=new Scanner(System.in); int N=input.nextInt(); while(N-->0){ n=input.nextInt(); max=0; f=new F[n]; for(int i=0;i<n;i++){ int x=input.nextInt(); int y=input.nextInt(); f[i]=new F(x,y); } for(int i=0;i<n;i++){ f[i].ok=false; dfs(f[i].wide,f[i].high,1); f[i].ok=true; } System.out.println(max); } } private static void dfs(int wide, int high, int sum) {//递归深度搜索 if(sum>max)//记录最大值 max=sum; for(int i=0;i<n;i++){ if(f[i].ok&&(f[i].wide<wide&&f[i].high<high||f[i].wide<high&&f[i].high<wide)){ f[i].ok=false; dfs(f[i].wide,f[i].high,sum+1); f[i].ok=true; } } } } class F{//存储长和宽,以及是否被用过 int wide,high; boolean ok=true; F(int wide,int high){ this.wide=wide; this.high=high; } F(){ } }
import java.util.Scanner; public class Main{//动态规划,Accepted 47MS 739 java 2013-07-23 23:39:06 static int g[][],t[],n; public static void main(String[] args) { Scanner input=new Scanner(System.in); int N=input.nextInt(); while(N-->0){ n=input.nextInt(); int a[]=new int[n]; int b[]=new int[n]; g=new int[n][n]; t=new int[n]; for(int i=0;i<n;i++){ a[i]=input.nextInt(); b[i]=input.nextInt(); } for(int i=0;i<n;i++) for(int j=0;j<n;j++) if((a[i]>a[j]&&b[i]>b[j])||(a[i]>b[j]&&b[i]>a[j])) g[i][j]=1; int max=-1; for(int i=0;i<n;++i) if(dp(i)>max) max=dp(i); System.out.println(max); } } private static int dp(int i) { int ans=t[i]; if(ans>0) return ans; ans=1; for(int j=0;j<n;++j) if(g[i][j]!=0) if(ans<dp(j)+1){ ans=dp(j)+1; t[i]=ans; } return ans; } }