Loading... 上午都是些概念啥的。。。 [](https://yueyangwu.cn/wp-content/uploads/2019/04/dp.png "从沙雕题看dp") <!--more--> * * * ### 下午。。。 #### 回文问题 * Q1:给定一个数列，求一个最长的回文子序列。 f\[i\]\[j\]:A\[i ~ j\]的最长回文子序列 ```cpp for (int i = 0; i < n; i++) f[i][i] = 1; for (int step = 2; step <= n; step++) { for (int i = 0; i + step - 1 < n; i++) { int j = i + step - 1; f[i][j] = max(f[i + 1][j], f[i][j - 1]); if (A[i] == A[j]) f[i][j] = max(f[i][j], f[i + 1][j - 1] + 2); } } ``` * Q2:给定一个数列，求回文子序列的个数 f\[i\]\[j\]:A\[i ~ j\]的回文子序列个数 用了个容斥原理emmmmmmmm ```cpp for (int i = 0; i < n; i++) f[i][i] = 1; for (int step = 2; step <= n; step++) { for (int i = 0; i + step - 1 < n; i++) { int j = i + step - 1; f[i][j] = f[i][j - 1] + f[i + 1][j] - f[i + 1][j - 1]; if (A[i] == A[j]) f[i][j] += f[i + 1][j - 1] + 1; } } ``` * * * #### 乌龟棋 [](http://yueyangwu.cn/wp-content/uploads/2019/04/图片1.png "1") [](http://yueyangwu.cn/wp-content/uploads/2019/04/图片2.png "2") 先使用一般的思路，可否使用下标作为状态？ 不行，因此使用每个类型卡牌的数量作为状态，定义$f[a][b][c][d]$为用a张1卡牌，b张2卡牌，c张3卡牌，d张4卡牌所得到的最高分数。这样可以判断当前位置$r=a+2\\times b+3\\times c+4\\times d$，再使用$w\[i\]$表示每个点的权值，即可得到状态转移方程： $f\[a\]\[b\]\[c\]\[d\]=max(f\[a\]\[b\]\[c\]\[d\],f\[a-1\]\[b\]\[c\]\[d\]+w\[r\])$ $f\[a\]\[b\]\[c\]\[d\]=max(f\[a\]\[b\]\[c\]\[d\],f\[a\]\[b-1\]\[c\]\[d\]+w\[r\])$ $f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+w[r])$ $f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+w[r])$ 最终答案即为$f[n][m][l][k]$,其中$n,m,l,k$分别为第$1,2,3,4$类型卡牌的张数。 * * * #### NlogN的sd题。。。 [](http://yueyangwu.cn/wp-content/uploads/2019/04/QQ截图20190429074813.png "sdt") ```cpp #include <iostream> using namespace std; int i,j,n,s,t,a[100001]; int main() { cin>>n; a[0]=-1000000; for(i=0;i<n;i++) { cin>>t; if(t>a[s]) a[++s]=t; else { int l=1,h=s,m; while(l<=h) { m=(l+h)/2; if(t>a[m]) l=m+1; else h=m-1; } a[l]=t; } } cout<<s<<endl; } ``` * sd题的nlogn告诉我们：有时候善用贪心规则可以优化 DP 的时间复杂度！ [](http://yueyangwu.cn/wp-content/uploads/2019/04/图片3.png "片段1") [](http://yueyangwu.cn/wp-content/uploads/2019/04/图片4.png "片段2") 通过分析该题目可知，本质上是求一个最长抖动序列。。。类似lca这样的算法，$O(n^2)$只能码70分，满分算法需要$O(nlogn)$ ```cpp #include<bits/stdc++.h> using namespace std; int a[1000009],f[1000009][2],n; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } f[1][0]=f[1][1]=1; for(int i=2;i<=n;i++){ if(a[i]>a[i-1]) f[i][0]=f[i-1][1]+1; if(a[i]<a[i-1]) f[i][1]=f[i-1][0]+1; if(a[i]<=a[i-1]) f[i][0]=f[i-1][0]; if(a[i]>=a[i-1]) f[i][1]=f[i-1][1]; } cout<<max(f[n][0],f[n][1]); return 0; } ``` Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏