清北学堂noip2019-DP图论-Day1

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


下午。。。

回文问题

  • Q1:给定一个数列,求一个最长的回文子序列。 f[i][j]:A[i ~ j]的最长回文子序列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×