UVA111 History Grading 简单的DP

这道题目有个地方很难，那就是题意，不知道是不是我的鸟语差，这道题目读起来要读很久才能理解，看到别人的博客也是有这样的吐槽，应该不是我的鸟语差，卖个关子就不说提议了，总是 是一个 LCS的问题，开的是一维的DP数组，要另外开一个记录当前的变化，如果开二维DP数组可能会更好理解一点，别人多数开的是二维的，我的跟某个大神的差不多 想到一维去了

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-7

#define inf 0xfffffff
const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
//

int answer[20+2];//正确答案
int now[20+2];//当前学生的排序
int dp[20+2];

int main() {
	int n,m;
	int ans;
	while(scanf("%d",&n) == 1) {
		for(int i=1;i<=n;i++)
			scanf("%d",&answer[i]);
		while(scanf("%d",&m) == 1) {
			ans = 0;
			now[m] = answer[1];
			for(int i=2;i<=n;i++) {
				scanf("%d",&m);
				now[m] = answer[i];
			}
			memset(dp,0,sizeof(dp));
			dp[1] = 1;
			for(int i=2;i<=n;i++) {
				dp[i] = 1;
				for(int j=1;j<i;j++)
					if(now[j] < now[i])
						dp[i] = max(dp[i],dp[j] + 1);
				if(dp[i] > ans)
					ans = dp[i];
			}
			printf("%d\n",ans);
		}
	}
	return EXIT_SUCCESS;
}

UVA111 History Grading 简单的DP

原文：http://blog.csdn.net/yitiaodacaidog/article/details/18325647