PAT-A1045(C/C++代码解析)

1045 Favorite Color Stripe (30 分)


注：散列，动态规划

1.LIS

#include 
#include 
#include 
using namespace std; 
const int maxn=300;
int hashtable[maxn];
int main ()
{
    int ans=-1,a,j,qq=0,i,w,n,b,m,x;
    memset (hashtable,-1,sizeof (hashtable));
    scanf ("%d %d",&w,&n);
    for (i=0;i=0)
		z[qq++]=b;
	}
	int dp[qq];
	for (i=0;idp[i])
    		{
    			dp[i]=dp[j]+1;
			}
		}
		ans=max(ans,dp[i]);
	}
	printf ("%d",ans);
    return 0;
}

2.LCS

#include 
#include 
#include 
using namespace std;  
const int maxn=10010;
int dp[maxn][maxn],a[maxn],b[maxn];
int main ()
{
    int e,i,n,m,j;
    a[0]=0,b[0]=0;
    scanf ("%d %d",&e,&n);
    for (i=1;i<=n;i++)
    scanf ("%d",&a[i]);
    scanf ("%d",&m);
    for (i=1;i<=m;i++)
    scanf ("%d",&b[i]);
    for (i=0;i