动态规划 - 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;