这几天在复习动态规划(DP),故在pat上找了两道dp的题目来练练手。
这一题看似跟动态规划扯不上,其实是可以把它看做动态规划问题——最长递增子序列(LIS)问题的一个变形。
题目中给定的第一个数组a[n],就相当于给定了“递增”的顺序。如果一个元素a[i]在a中的下标大于或等于另一个元素a[j](i>=j),我们就称a[i]>a[j]
故只需把原来LIS问题中的判断大小部分改为现在的判定大小的规则,基本就可以了。
还有几个注意点:出现在b[m]里,但a[n]里没有的元素,他们是没有顺序的,我们可以直接忽略这样的元素。
代码如下(建议先去看一看LIS问题再来看这一道题):
#include <iostream> #include <fstream> using namespace std; int N, M, P; int *a; int *b; int *L; int *stp; const int MINNUM = -999; bool compare(int tmp1, int tmp2) { if(stp[tmp2 - 1] == -1) return false; if(stp[tmp1 - 1] >= stp[tmp2 - 1]) return true; else return false; } bool isExist(int tmp) { if(stp[tmp - 1] != -1) return true; return false; } void LIS() { for(int j = 0; j < P; j++) { int max = MINNUM; if(!isExist(b[j])) continue; for(int p = 0; p < j; p++) { if(compare(b[j], b[p])) max = max > L[p] ? max : L[p]; } if(max == MINNUM) continue; else L[j] = max + 1; } } int main() { //fstream cin("a.txt"); cin>>N>>M; stp = new int[N]; for(int i = 0; i < N; i++) stp[i] = -1; a = new int[M]; int tmp = 0; while (tmp < M) { cin>>a[tmp]; stp[a[tmp] - 1] = tmp; tmp++; } cin>>P; b = new int[P]; tmp = 0; while (tmp < P) { cin>>b[tmp]; tmp++; } L = new int[P]; for(int i = 0; i < P; i++) if(isExist(b[i])) L[i] = 1; else L[i] = -1; LIS(); int maxnum = -2; for(int i = 0; i < P; i++) if(L[i] > maxnum) maxnum = L[i]; if(maxnum > 0) cout<<maxnum<<endl; else cout<<0<<endl; //system("Pause"); }