晋江科技馆集训Day 4

二分查找(CSP-J)和DP(CSP-S)

二分查找

以下参考OI-Wiki

定义

二分查找是用来在一个有序数组中查找某一元素的算法

框架

可见CSDN

二分查找例题

d

DP可见这篇博客

简单DP

简单DP例题

e.g. Hills And Valleys(HDU6357)

由于是英文,考虑到有些人可能看不懂,我还是把中文的题目打出来吧😭(我都装得这么可怜了，还不快谢谢我~😏)

题目描述
Tauren有一个长度为n的整数序列A(从1开始).他想要翻转A的一个区间l,r,以使A的最长不下降子序列的长度最大化.找到最大长度和任何实现该任务的翻转方式.
长度为m的不下降子序列可以表示为A_x1,A_x2,⋯,A_xm，其中1≤x1<x2<⋯<xm≤n且A_x1≤A_x2≤⋯≤A_xm。

输入
第一行包含一个整数T，表示测试用例的数量
以下行描述了所有测试用例。对于每个测试用例：
第一行包含一个整数n
第二行包含n个整数A₁,A₂,⋯,A_n,没有空格
1≤T≤100，1≤n≤10⁵，0≤A[i]≤9(i=1,2,⋯,n)
保证所有测试用例中n的总和不超过2*10⁵

输出
对于每个测试用例,在一行中以三个空格分隔的整数m,l和r,其中m表示最大长度,[l,r]表示要翻转的相关区间

`示例输入``

2
9
864852302
9
203258468

示例输出

5 1 8
6 1 2

提示
在第一个示例中，翻转[1,8]后的序列为032584682，其中一个最长不下降子序列是03588。
在第二个示例中，翻转[1,2]后的序列为023258468，其中一个最长不下降子序列是023588。

来源
2018年多大学训练比赛5

以下是来自博客园better46的代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100005
int n,b[19];
char str[N];
int a[N],dp[N][19],pre[N][15];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int ans=0,ansl,ansr; scanf("%d %s",&n,str);
        for(int i=0;i<n;i++) a[i+1]=str[i]-'0';
        for(int L=0;L<=9;L++)
        for(int R=L;R<=9;R++){
            int tot=0;
            for(int k=0;k<=L;k++) b[++tot]=k;
            for(int k=R;k>=L;k--) b[++tot]=k;
            for(int k=R;k<=9;k++) b[++tot]=k;
            //更新LCS
            for(int i=1;i<=n;i++)
            {
                int t=0;
                for(int j=1;j<=tot;j++)
                {
                    if(dp[i-1][j]>dp[i-1][t]) t=j;
                    pre[i][j]=t;
                    dp[i][j]=dp[i-1][t]+(a[i]==b[j]);
                }
            }
            for(int j=tot;j>=1;j--)
            if(dp[n][j]>ans){
                ans=dp[n][j];
                int t=j,l=0,r=0;
                for(int i=n;i>=0;i--){
                    if(!l&&t<=L+1) l=i+1;
                    if(!r&&t<=R+2) r=i;
                    t=pre[i][t];
                }
                if(r==0) r=l;
                ansl=l;ansr=r;
            }
        }
         printf("%d %d %d\n",ans,ansl,ansr);
    }
    return 0;
}

来点看起来更直观的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
const int maxm=20+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,a[maxn],dp[maxn][maxm],b[maxm];
int ans,L,R,l,r,h;
int al[maxn][maxm],ar[maxn][maxm];
int solve()
{
    for(int i=0;i<=h;i++)
        dp[0][i]=0;//初始化
    for(int i=1;i<=n;i++){//a和b匹配
        for(int j=1;j<=h;j++){
            dp[i][j]=dp[i-1][j];
            al[i][j]=al[i-1][j];//记录左端点
            ar[i][j]=ar[i-1][j];//记录右端点
            if(a[i]==b[j]){//如果有相等的情况，+1
                dp[i][j]=dp[i-1][j]+1;
                if(l==j&&!al[i][j])//如果当前的j就是b开始翻转的左端点,更新记录
                    al[i][j]=i;
                if(r==j)//右端点
                    ar[i][j]=i;
            }
            if(dp[i][j-1]>dp[i][j]){//更新答案
                dp[i][j]=dp[i][j-1];
                al[i][j]=al[i][j-1];
                ar[i][j]=ar[i][j-1];
            }
        }
    }
    return dp[n][h];
}
char s[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%s",&n,s+1);
        for(int i=1;i<=n;i++)
            a[i]=s[i]-'0';
        h=0;
        for(int i=0;i<=9;i++)
            b[++h]=i;
        L=R=l=r=1;
        ans=solve();
        for(int i=0;i<=9;i++){
            for(int j=i+1;j<=9;j++){
                h=0;
                for(int k=0;k<=i;k++)
                    b[++h]=k;//翻转区间的左部分不变
                l=h+1;
                for(int k=j;k>=i;k--)//要翻转的区间把数字翻转
                    b[++h]=k;
                r=h;
                for(int k=j;k<=9;k++)//反转区间的右部分不变
                    b[++h]=k;
                int tmp=solve();
                if(ans<tmp&&al[n][h]&&ar[n][h]){//更新结果
                    ans=tmp;
                    L=al[n][h];
                    R=ar[n][h];
                }
            }
        }
        printf("%d %d %d\n",ans,L,R);
    }
}

看着引入的这一大串的库,好吧,我承认,我知难而退了,这什么脏东西!

尽管有些难,但想通了还是勉勉强强可以做的

所以,这伟大的任务就交给你们了!

树形DP

树形DP框架

void dfs(节点u){
     for(){   / /循环访问所有u的子节点
     dfs(u的子节点);
     用u的子节点信息更新节点u的信息;
     }
}

树形DP例题

e.g. Destruction of a Tree(CF 963 B)

这题除了用树形DP还能用DFS解决,点此处前去查看DFS解法