DP

magic balls

2
5 3
5 1
4 2
3 1
2 4
3 1
5 4
5 1
4 2
3 1
2 4
3 1

4
4

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=1111;

int n,m;
int a[maxn],b[maxn];
int dp[maxn][maxn][2];

int main()
{
	int T_T;
	scanf("%d",&T_T);
	while(T_T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",a+i,b+i);
		}
		memset(dp,-1,sizeof(dp));
		dp[0][0][0]=0;
		for(int i=1;i<=n;i++)
		{
			dp[i][0][0]=1; dp[i][1][1]=1;
			for(int j=1;j<i;j++)
			{
				int e=min(j,m);
				if(a[i]>a[j])
				{
					for(int k=0;k<=e;k++)
					{
						if(dp[j][k][0]>=0) 
							dp[i][k][0]=max(dp[i][k][0],dp[j][k][0]+1);
					}
				}
				if(a[i]>b[j])
				{
					for(int k=0;k<=e;k++)
					{
						if(dp[j][k][1]>=0) 
							dp[i][k][0]=max(dp[i][k][0],dp[j][k][1]+1);
					}
				}
				if(b[i]>a[j])
				{
					for(int k=0;k<=e;k++)
					{
						if(dp[j][k][0]>=0) 
							dp[i][k+1][1]=max(dp[i][k+1][1],dp[j][k][0]+1);
					}
				}
				if(b[i]>b[j])
				{
					for(int k=0;k<=e;k++)
					{
						if(dp[j][k][1]>=0) 
							dp[i][k+1][1]=max(dp[i][k+1][1],dp[j][k][1]+1);
					}
				}
			}
		}
		int ans=1;
		for(int i=1;i<=n;i++)
		{
			int e=min(i,m);
			for(int j=0;j<=e;j++)
			{
				ans=max(ans,max(dp[i][j][0],dp[i][j][1]));
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

HDOJ 5125 magic balls DP

原文：http://blog.csdn.net/ck_boss/article/details/41723845