2019.5.3&4高中部集训

这次因为期中考没去，现在发现这次学的 $dp$ 好难啊，应该是一直在做题吧 $qwq$

知识清单

$DP$ 动态规划

笔记&&解题报告

基本问题：

~~$01$ 背包~~（似乎没讲）
最长上升子序列
- $O(n^2)$ ：最暴力算法直接 $O(n^2)$ ，查找前面可转移的最长上升序列转移，这一查找步骤使用for，所以慢。
- $O(n \log n)$ ：使用一个栈来储存转移点，如果一个数比栈中所有数大，直接压入 $top$ ，否则找到相应的位置替换，这样寻找转移点可以直接二分（ $O(\log n)$ ），栈中的元素满足单调性。
最大子段和
- $O(n)$ ：分为贪心和 $dp$ ，~~可以理解为一个背包问题（即捡或不捡）~~（不能这么理解 $qwq$ ，中途不捡就不是子段了），扫一遍即可，更新最大值。
- $O(n \log n)$ ：数据结构，不过这种适用于动态查询，即可能被修改。
最长公共子序列
- $O(n^2)$ ： $O(n^2)$ 的方法用于全部情况，直接两遍for就可以了，先从前一个位置转移，然后相同就加 $1$ ，不相同不处理，一直传下去。最后一个就是答案。
- $O(n \log n)$ ：特殊的，如果两个互相匹配的序列皆为数字，我们可以优化到 $O(n \log n)$ 。我们用一个数组来保存第一个串在第二个串中所对应的各元素的位置。因为只有在位置保持上升时，这才能在原串中组成子序列。所以答案就是这个数组的最长上升子序列。 $Code$

例题

逆序对数列

分析：（~~上次写过这道题（SP64）~~）那道题和这道题不一样的，这道题还带一个前缀和优化。可以发现，朴素的做法是 $O(nk^2)$ 的，在这道题的数据会超时。然后又会发现，第 3 层循环的作用就是把 $f[i][...]$ 加起来，所以说可以想到前缀和的做法。详情见题解。

还有，记得要取模！

#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e3+5;
const int Mod = 1e4;
int n, k, f[MAXN][MAXN];

int main() {
    scanf ("%d%d",&n,&k);
    
    f[1][0]=1;
    
    for (int i=2; i<=n; i++) {
        int sum = 0;
        for (int j=0; j<=k; j++) {
            sum += f[i-1][j];
            sum %= Mod;
            f[i][j]=sum;
            if ( j-i+1 >= 0 ) {
                sum = ( sum-f[i-1][j-i+1]+Mod )%Mod;
            }
        }
    }
    
    printf ("%d\n",f[n][k]);
    return 0;
}

最长公共子序列：上面写过了 $\Uparrow \Uparrow$

[[ $SHOI$ ]股票交易](https://www.luogu.org/problemnew/show/P2569)

分析：懒得写了~~（根本不会）~~， $Sooke$ 的题解。然后老师 $PPT$ 上列了一个转移方程：（雾）

f_{i,j}=\max\limits_{k \in[0,maxP],t \in[0,i-w]}(f_{t,k}+sell_-or_-buy(i,j-k))

时间复杂度： $O(n^3)$

添加括号

分析：发现这道题让你添加括号就是改变合并顺序，所以想到区间 $dp$ ，区间 $dp$ 最经典的题就是石子合并，这题也是只让你合并相邻的两个，计算最小代价。

[[ $SHOI2001$ ]三国围棋对抗赛](https://www.luogu.org/problemnew/show/P2531)

分析：这题挺冷的，没什么人做，看到数据范围就可以先想到用“暴力”了，这题算的全是概率，所以什么时候加，什么时候乘不要搞错了，前面有个轮空规则不要忘了（应该不会吧 $qwq$ ），然后差不多就是一个接近于模拟的一个 $dp$ 。~~众所周知~~， $dp$ 可以使用任何方法，递归也是可以的，就像上次学校考试中的 $T5$ ， $std$ 使用的就是 $dfs$ （递归） $+dp$ 。

Code

：

#include <cstdio>
#include <iostream>
using namespace std;
double data[16][11],b[6][6],win[6][6][6],f[3][7][7][7];
int t,n;
double ans=0,tot=0;
bool book[16];
void dfs(int p) {
    if(p>5) {
        f[0][1][1][1]=f[1][1][1][1]=f[2][1][1][1]=1.0/3.0;
        for(int i=1; i<=6; i++) {
            for(int j=1; j<=6; j++) {
                for(int k=1; k<=6; k++) {
                    if(i>1) {
                        f[0][i][j][k]=f[1][i-1][j][k]*win[4][k][i-1]+f[2][i-1][j][k]*win[2][j][i-1];
                        if(i==6)
                            f[0][i][j][k]+=f[0][i][j-1][k]*win[5][k][j-1]+f[0][i][j][k-1]*win[3][j][k-1];
                    }
                    if(j>1) {
                        f[1][i][j][k]=f[0][i][j-1][k]*win[5][k][j-1]+f[2][i][j-1][k]*win[0][i][j-1];
                        if(j==6)
                            f[1][i][j][k]+=f[1][i-1][j][k]*win[4][k][i-1]+f[1][i][j][k-1]*win[1][i][k-1];
                    }
                    if(k>1) {
                        f[2][i][j][k]=f[0][i][j][k-1]*win[3][j][k-1]+f[1][i][j][k-1]*win[1][i][k-1];
                        if(k==6)
                            f[2][i][j][k]+=f[2][i-1][j][k]*win[2][j][i-1]+f[2][i][j-1][k]*win[0][i][j-1];
                     }
                }
            }
        }
        tot=0;
        for(int i=1; i<=5; i++) {
            tot+=f[1][i][6][6];
        }
        ans=max(ans,tot);
        return;
    }
    int l,r;
    for(l=1; l<=n; l++) {
         if(!book[l]) {
            book[l]=true;
            for(r=1; r<=5; r++) {
                win[0][p][r]=data[l][r];
                win[2][r][p]=1.0-data[l][r];
            }
            for(r=1; r<=5; r++) {
                win[1][p][r]=data[l][r+5];
                win[4][r][p]=1.0-data[l][r+5];
            }
            dfs(p+1);
            book[l]=false;
        }
    }
    return;
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=10; j++)
            scanf("%lf",&data[i][j]);
    for(int i=1; i<=5; i++) {
        for(int j=1; j<=5; j++) {
            scanf("%lf",&b[i][j]);
            win[3][i][j]=b[i][j];
            win[5][j][i]=1.0-b[i][j];
        }
    }
    dfs(1);
    printf("%.6lf\n",ans);
    return 0;
}