上午都是些概念啥的。。。 从沙雕题看dp

    • *

下午。。。

回文问题

  • Q1:给定一个数列,求一个最长的回文子序列。 f[i][j]:A[i ~ j]的最长回文子序列
    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
    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;
        }
    }
    • *

乌龟棋

1 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题。。。

sdt

    #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 的时间复杂度!

片段1 片段2 通过分析该题目可知,本质上是求一个最长抖动序列。。。类似lca这样的算法,$O(n^2)$只能码70分,满分算法需要$O(nlogn)$

    #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 14th, 2020 at 09:02 pm