动态规划 - DP

（一）动态规划入门

一、动态规划入门

例题1：数字三角形 Luogu P1216

状态：\(f[i][j]\)：第 \(i\) 行第 \(j\) 列上点到最后一行的最大和

状态转移：\(f[i][j] = max(f[i-1][j],f[i-1][j-1])+a[i][j]\)

for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++)
        f[i][j]=f[i][j]+max(f[i-1][j-1],f[i-1][j]);
sort(f[n]+1,f[n]+1+n);
printf("%d\n",f[n][n]);

例题2：公交乘车

一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。

例如下表就是一个费用的单子。

公里数	1	2	3	4	5	6	7	8	9	10
价格	12	21	31	40	49	58	69	79	90	101

没有一辆车子行驶超过\(10\)公里，一个顾客打算行驶 \(n\) 公里（\(1<=n<=100\)）

它可以通过无限次的换车来完成旅程。最后要求费用最少。

状态：\(f[i]\)：前 \(i\) 公里的最小花费

状态转移：\(f[i] = min(f[i],f[i-j]+a[j])\)

for(int i=2;i<=n;i++)
{
    for(int j=1;j<=10;j++)
    {
        if(i-j<0) continue;
        f[i]=min(f[i],f[i-j]+a[j]);
    }
}

练习1：摘花生

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地（如下图），从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生

经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

状态：\(f[i][j]\)：从出发点到 \((i,j)\) 能够采花生的最大个数

状态转移：\(f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j]\)

for(int i=1;i<=r;i++)
    for(int j=1;j<=c;j++)
        f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
printf("%d\n",f[r][c]);

练习2：黑熊过河

有一只黑熊想过河，但河很宽，黑熊不会游泳，只能借助河面上的石墩跳过去。

它可以一次跳一墩，也可以一次跳两墩，

但是每跳一次都会耗费一定的能量，黑熊最终可能因能量不够而掉入水中。

所幸的是，有些石墩上放了一些食物，些食物可以给黑熊增加一定的能量。

问黑熊能否利用这些石墩安全地抵达对岸？请计算出抵达对岸后剩余能量的最大值。

状态：\(f[i]\)：黑熊在第 \(i\) 个石头时拥有的最大能量

状态转移：\(f[i]=max(f[i-1],f[i-2])+a[i]-q\)

初值：\(f[0]=p,f[1]=p-q+a[1];\)

for(int i=2;i<=n+1;i++)
{
    if(f[i-1]-q<0&&f[i-2]-q<0)
    {
        printf("NO\n");
        return 0;
    }
    if(f[i-1]-q<0) f[i-1]=0;
    if(f[i-2]-q<0) f[i-2]=0;
    f[i]=max(f[i-1],f[i-2])-q+a[i];		
}
printf("%d\n",f[n+1]);

二、最长子序列问题 - LIS

例题1：LIS模板题

有 \(N\) 个整数，输出这 \(N\) 个整数的最长上升序列、

最长下降序列、最长不上升序列和最长不下降序列。

以最长上升序列为例：

状态：\(f[i]\)：长度为 \(i\) 的上升子序列末尾元素的最小值

状态转移：当 \(j>i\) 且 \(f[i] \geq a[j]\) 时，\(f[i] = a[j]\)

初值：\(f[i] = INF,f[1] = a[1]\)

for(int i=1;i<=n;i++)
    b[i]=a[i];

//上升 
for(int i=1;i<=n;i++)
    a[i]=b[i];
for(int i=1;i<=n+1;i++)
    f[i]=INF;
f[1]=a[1];
for(int i=2;i<=n;i++)
    *lower_bound(f+1,f+n+1,a[i])=a[i];
int ans1=lower_bound(f+1,f+2+n,INF)-(f+1);

//不下降 
for(int i=1;i<=n;i++)
    a[i]=b[i];
for(int i=1;i<=n+1;i++)
    f[i]=INF;
f[1]=a[1];
for(int i=2;i<=n;i++)
    *upper_bound(f+1,f+n+1,a[i])=a[i];
int ans2=lower_bound(f+1,f+2+n,INF)-(f+1);

//下降 
for(int i=1;i<=n;i++)
    a[i]=b[i]*-1;
for(int i=1;i<=n+1;i++)
    f[i]=INF;
for(int i=2;i<=n;i++)
    *lower_bound(f+1,f+n+1,a[i])=a[i];
int ans3=lower_bound(f+1,f+2+n,INF)-(f+1);

//不上升
for(int i=1;i<=n;i++)
    a[i]=b[i]*-1;
for(int i=1;i<=n+1;i++)
    f[i]=INF;
f[1]=a[1];
for(int i=2;i<=n;i++)
    *upper_bound(f+1,f+n+1,a[i])=a[i];
int ans4=lower_bound(f+1,f+2+n,INF)-(f+1);

printf("%d\n%d\n%d\n%d\n",ans1,ans3,ans4,ans2); 

例题2：导弹拦截 Luogu P1020 [NOIP1999 普及组]

根据题意，找出最长不上升和上升子序列即可。

for(int i=1;i<=n;i++)
	b[i]=a[i];

for(int i=1;i<=n;i++)
    a[i]=b[i]*-1;
for(int i=1;i<=n+1;i++)
    f[i]=INF;
f[1]=a[1];
for(int i=2;i<=n;i++)
    *upper_bound(f+1,f+n+1,a[i])=a[i];
int ans1=lower_bound(f+1,f+2+n,INF)-(f+1);

for(int i=1;i<=n;i++)
    a[i]=b[i];
for(int i=1;i<=n+1;i++)
    f[i]=INF;
f[1]=a[1];
for(int i=2;