动态规划Dynamic Programming
noco
2018-04-01 16:57:58
# 动态规划 #
## 一.模型 ##
**填表法**就是利用状态转移方程和上一个状态来推导出现在的状态（相当于知道已知条件，将答案填入）
**刷表法**就是利用当前的状态，把有关联的下一状态都推出来。
#### 1.线性模型 ####
线性模型的是动态规划中最常用的模型，上文讲到的最长单调子序列就是经典的线性模型，这里的线性指的是状态的排布是呈线性的。【例题6】是一个经典的面试题，我们将它作为线性模型的敲门砖。
> 【例题6】在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。
每次过桥的时候最多两个人，如果桥这边还有人，那么还得回来一个人（送手电筒），也就是说N个人过桥的次数为2*N-3
（倒推，当桥这边只剩两个人时只需要一次，三个人的情况为来回一次后加上两个人的情况...）。有一个人需要来回跑，将手电筒送回来（也许不是同一个人，really？！）这个回来的时间是没办法省去的，并且回来的次数也是确定的，为N-2，如果是我，我会选择让跑的最快的人来干这件事情，但是我错了...如果总是跑得最快的人跑回来的话，那么他在每次别人过桥的时候一定得跟过去，于是就变成就是很简单的问题了，花费的总时间：
> ** T = minPTime * (N-2) + (totalSum-minPTime)**
来看一组数据 四个人过桥花费的时间分别为 1 2 5 10，按照上面的公式答案是19，但是实际答案应该是17。
具体步骤是这样的：
1. 第一步：1和2过去，花费时间2，然后1回来（花费时间1）；
1. 第二歩：3和4过去，花费时间10，然后2回来（花费时间2）；
1. 第三步：1和2过去，花费时间2，总耗时17。
所以之前的贪心想法是不对的。
我们先将所有人按花费时间递增进行排序，假设前i个人过河花费的最少时间为opt[i]，那么考虑前i-1个人过河的情况，即河这边还有1个人，河那边有i-1个人，并且这时候手电筒肯定在对岸，所以
> **opt[i] = opt[i-1] + a[1] + a[i] **
(让花费时间最少的人把手电筒送过来，然后和第i个人一起过河)
如果河这边还有两个人，一个是第i号，另外一个无所谓，河那边有i-2个人，并且手电筒肯定在对岸，所以
> opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2]
(让花费时间最少的人把电筒送过来，然后第i个人和另外一个人一起过河，
由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，
送过来后花费最少的和花费次少的一起过河，解决问题)
所以
** opt[i] = min{opt[i-1] + a[1] + a[i] ,opt[i-2] + a[1] + a[i] + 2*a[2] } **
#### 2.区间模型 ####
区间模型的状态表示一般为d[i][j]，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。
>
> 【例题7】给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。
典型的区间模型，回文串拥有很明显的子结构特征，即当字符串X是一个回文串时，在X两边各添加一个字符'a'后，aXa仍然是一个回文串，我们用d[i][j]来表示A[i...j]这个子串变成回文串所需要添加的最少的字符数，那么对于A[i] == A[j]的情况，很明显有
** d[i][j] = d[i+1][j-1] **
（这里需要明确一点，当i+1 j-1时也是有意义的，它代表的是空串，空串也是一个回文串，所以这种情况下d[i+1][j-1] = 0）；
当A[i] != A[j]时，我们将它变成更小的子问题求解，我们有两种决策：
1. 在A[j]后面添加一个字符A[i]；
1. 在A[i]前面添加一个字符A[j]；
根据两种决策列出状态转移方程为：
> ** d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1; **
> (每次状态转移，区间长度增加1)
空间复杂度O(n^2)，时间复杂度O(n^2)， 下文会提到将空间复杂度降为O(n)的优化算法。
### [博客原址](http://www.cppblog.com/menjitianya/archive/2015/10/23/212084.html "博客原文")
------------
# 题目#
## 一、传纸条##
[原址](https://www.luogu.org/problemnew/show/P1006)
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int N=200;
int m,n;
int cla[N][N];
int f[N][N][75];//直接储存和
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&cla[i][j]);
f[1][1][1]=0;//出发点赋初值为0
for(int i=1;i<=n+m;i++)//限制一：路径数最大值 i为路径长度
for(int j=1;j<=m&&j<=i;j++)//限制二：行数 j&&k都是
for(int k=1;k<=m&&k<=i;k++)
//这里的j是搜到第i个同学时 第j行去路径所能求得的最大值
// 这里的k是搜到第i个同学时 第k行去路径所能求得的最大值
if(j!=k||i==n+m){//前者判重 后者保证搜完有输出 即到达终点时要再次计算
f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);//每个都从上一个推来
f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]);
f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]);
f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]);
f[i][j][k]+=cla[j][i-j+1]+cla[k][i-k+1];//加和 后一下标由路径可简单推得
}
printf("%d\n",f[n+m][m][m]);
return 0;
}
```
## 二、统计单词个数 ##
[原址](https://www.luogu.org/problemnew/show/P1026)
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e3;
const int inf=0x7fffff;
int p,k,n;
char ar[N*100];//存文章
char b[N][N];//存字典
int len[N];//存字典中单词长度
int ne[N];//存文章中匹配字典中单词的尾下标
int f[N][N];//存i个字符前j个分割所能取得的最大单词数
inline void get_pre(){
ne[0]=inf;
for(int i=1;i<=p*20;i++){
int minn=inf;
for(int j=1;j<=n;j++){//字典中单词数目
int l=i;//前指针
bool flag=false;//是否可以匹配 true=不可，false=可
for(int q=0;q<len[j];q++)//字典中单词长度
if(ar[l++]!=b[j][q]){
flag=true;
break;
}
if(!flag)minn=i+len[j]-1;//求尾标
}
ne[i]=minn;
}
}//其实就是个暴力匹配
inline void work(){
for(int i=1;i<=p*20;i++){//遍历整个串
for(int j=1;j<=k;j++){//枚举分割数
int word=0;//这一次分割可得到的单词数量
for(int q=i;q>=j;q--){//枚举分割段长度
if(ne[q]<=i)word++;//由题意可知
f[i][j]=max(f[i][j],f[q-1][j-1]+word);//分析可知 此次数量可从上一个k-1的推过来 长度亦然
}
}
}
}
int main(){
scanf("%d%d",&p,&k);
for(int i=1;i<=p*20;i++)cin>>ar[i];
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>b[i];
len[i]=strlen(b[i]);
}
get_pre();
work();
printf("%d\n",f[p*20][k]);
return 0;
}
```
## 三、相似基因 ##
[原址](https://www.luogu.org/problemnew/show/P1140)
f[i][j]:字符串s1的前i个与字符串s2的前j个匹配所能达到的最大匹配值（不计算空碱基）
### **思路**
1.打表
2.dp
- ### 伪代码
- **f[i][j]=max(f[i][j],f[i-1][j]+（s2[j]与空碱基匹配的值）**
- **f[i][j-1]+(s1[i]与空碱基匹配的值),f[i-1][j-1]+(s1[i]与s2[j]匹配值))**
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
const int N=120;
int n,m;
int a[N],b[N];
char s1[N],s2[N];
int f[N][N];
int p[6][6]={
{0},
{0,5,-1,-2,-1,-3},
{0,-1,5,-3,-2,-4},
{0,-2,-3,5,-2,-2},
{0,-1,-2,-2,5,-1},
{0,-3,-4,-2,-1,0}
};
inline int change(char c){//将字符转化为序号
if(c=='A') return 1;
if(c=='C') return 2;
if(c=='G') return 3;
return 4;
}
int l1,l2;
inline void init(){
for(int i=1;i<=l1;i++)
for(int j=1;j<=l2;j++)
f[i][j]=INT_MIN;
for(int i=1;i<=l1;i++)a[i]=change(s1[i]);
for(int i=1;i<=l2;i++)b[i]=change(s2[i]);
for(int i=1;i<=l1;i++)f[i][0]=f[i-1][0]+p[a[i]][5];
for(int i=1;i<=l2;i++)f[0][i]=f[0][i-1]+p[b[i]][5];
}
int main(){
scanf("%d%s%d%s",&l1,s1+1,&l2,s2+1);
init();
for(int i=1;i<=l1;i++)
for(int j=1;j<=l2;j++){
f[i][j]=max(f[i][j],f[i][j-1]+p[b[j]][5]);
f[i][j]=max(f[i][j],f[i-1][j]+p[a[i]][5]);
f[i][j]=max(f[i][j],f[i-1][j-1]+p[a[i]][b[j]]);
}
printf("%d\n",f[l1][l2]);
return 0;
}
```
## 四、垃圾陷阱 ##
[原址](https://www.luogu.org/problemnew/show/P1156)
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=150;
int d,g;
int f[N];//达到此高度时 生存时间长度
struct cow{
int t,l,h;
//t表示垃圾被投进井中的时间 l表示该垃圾能维持卡门生命的时间 h该垃圾能垫高的高度
}c[N];
inline bool cmp(cow a,cow b){return a.t<b.t;}
//贪心的按维持时间排序
int main(){
memset(f,-1,sizeof(f));
f[0]=10;//初始化 体内十小时能量
scanf("%d%d",&d,&g);
for(int i=1;i<=g;i++)scanf("%d%d%d",&c[i].t,&c[i].l,&c[i].h);
sort(c+1,c+g+1,cmp);
for(int i=1;i<=g;i++){
for(int j=d;j>=0;j--){
if(f[j]>=c[i].t){//懒得取min
if(j+c[i].h>=d){
printf("%d\n",c[i].t);
return 0;//如果能出去就出去 即最早可什么时候爬出
}else{//否则继续
f[j+c[i].h]=max(f[j],f[j+c[i].h]);
//高度+这个垃圾的高度的生命值=max(d到0的生命值)，即不吃垃圾用它来堆
f[j]+=c[i].l;//存下存活时间 此时高度+=这个垃圾的高度
}
}
}
}//01背包
printf("%d\n",f[0]);//0即不能出去的最长生存时间
return 0;
}
```
## 五、尼克的任务 ##
[原址](https://www.luogu.org/problemnew/show/P1280)
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4+500;
int n,k;
int sum[N],num=1;
int f[N];
struct seg{int s,e;}a[N];
inline bool cmp(seg a,seg b){return a.s>b.s;}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++){
scanf("%d%d",&a[i].s,&a[i].e);
sum[a[i].s]++;
}
sort(a+1,a+k+1,cmp);//贪心的排个序
for(int i=n;i>=1;i--){
if(sum[i]==0)f[i]=f[i+1]+1;
else
for(int j=1;j<=sum[i];j++){
if(f[a[num].e+i]>f[i])
f[i]=f[a[num].e+i];
num++;
}
}
printf("%d\n",f[1]);
return 0;
}
//f[i]=f[i+1]+1;继承上一个时刻的最大空闲时间后+1
//f[i]=max(f[i],f[i+a[sum])
//a[sum]表示在这个时刻的任务的持续时间，找出选择哪一个本时刻任务使空闲时间最大化
```
## 六、多米诺骨牌 ##
[原址](https://www.luogu.org/problemnew/show/P1282)
### 思路 ###
1. f[i][j][k]表示前i个上面j个下面k个
2. 但是发现j+k即总数是个定值
优化到 f[i][j]
3. 再循环处理最优值
转移方程也很好想了
**f[i][j]=min{f[i-1][j],f[i-1][j+up[i]-down[i]]) **
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
const int N=1e4;
const int inf=0x3ff;
int n;
int up[N],d[N],f[1500][N];
int sum,upp,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&up[i],&d[i]);
sum+=d[i]+up[i];//预处理出一个总和
upp+=up[i];//上界
}
memset(f,0x3f,sizeof(f));
f[0][upp]=0;//初始化
for(int i=1;i<=n;i++)
for(int j=1;j<=sum;j++){
if(j-up[i]+d[i]<0)continue;//把负数判断掉 c++中数组没有负下标
f[i][j]=min(f[i-1][j],f[i-1][j+up[i]-d[i]]+1);
}
int upline=N;
for(int i=sum;i>=0;i--)
if(abs(sum-i-i)<upline&&f[n][i]<inf){
upline=abs(sum-i-i);//注意取绝对值
ans=f[n][i];//更新ans
}
printf("%d\n",ans);
return 0;
}
```
## 七、最大正方形 ##
[原址](https://www.luogu.org/problemnew/show/P1387)
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=500;
int n,m;
int sq[N][N];
int ans;
int f[N][N];//表示以sq[i][j]为右下角的矩阵的最大值
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&sq[i][j]);
for(int i=0;i<n;i++){
f[i][0]=sq[i][0];
f[0][i]=sq[0][i];
}//一定要先预处理边界
for(int i=1;i<n;i++)//扫过整个矩阵
for(int j=1;j<m;j++)
if(sq[i][j]){//当前点不是障碍
f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;
ans=max(ans,f[i][j]);
}
printf("%d\n",ans);
return 0;
}
```
## 八、烹调方案 ##
[原址](https://www.luogu.org/problemnew/show/P1417)
### 思路
类似于kkk的 分析一下整个过程 可知最优解是符合**某种顺序**的
由此 进行以下分析：
- 现在考虑相邻的两个物品x,y。
假设现在已经耗费p的时间，
那么分别列出先做x,y的代价：
a[x]-(p+c[x])*b[x]+a[y]-(p+c[x]+c[y])*by
a[y]-(p+c[y])*b[y]+a[x]-(p+c[y]+c[x])*bx
- 对这两个式子化简，得到①＞②的条件是
> **c[x]*b[y]<c[y]*b[x]**
- 发现只要满足这个条件的物品对(x,y)，x在y前的代价永远更优。
因此可以根据这个条件进行**排序**，之后就是~~简单的~~**01背包**了。
show me the code!!!
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long//开long long还是必要的
using namespace std;
const int N=1e5+500;
int T,n;
ll f[N],ans;
struct foot{int a,b,c;}a[N];
bool cmp(foot a,foot b){return (ll)a.c*(ll)b.b<(ll)b.c*(ll)a.b;}
int main(){
scanf("%d%d",&T,&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i].a);
for(int i=1;i<=n;i++)scanf("%d",&a[i].b);
for(int i=1;i<=n;i++)scanf("%d",&a[i].c);
sort(a+1,a+n+1,cmp);//排序 上文有讲
memset(f,500,sizeof(f));
f[0]=0;//初始化
for(int i=1;i<=n;i++)
for(int j=T;j>=0;--j)
if(f[j]!=-1&&j+a[i].c<=T)
f[j+a[i].c]=max(f[j+a[i].c],f[j]+(ll)a[i].a-(ll)(j+a[i].c)*(ll)a[i].b);//注意进行强制转换
for(int i=0;i<=T;i++)ans=max(ans,f[i]);
printf("%lld\n",ans);
return 0;
}
```
## 九、Likecloud-吃、吃、吃 ##
[原址](https://www.luogu.org/problemnew/show/P1508)
#### ~~手动滑稽~~ 题目背景好有趣 QAQ
问世间，青春期为何物？答曰：“甲亢，甲亢，再甲亢；挨饿，挨饿，再挨饿！”
### 思路
其实就是个三向搜索的数字三角形
~~我十分钟就切了~~
找好**边界**和**初位置**就好啦
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=500;
int ans;
int m,n;
int sq[N][N];
int f[N][N];
int main(){
scanf("%d%d",&m,&n);
memset(sq,-10000,sizeof(sq));//实践证明 这步初始化是十分重要的
//这也就是边界啦 不先赋值为一个极大的负数 会跑出去
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&sq[i][j]);
int mid=(n>>1)+1;//找找数字三角形的顶 其实是水牛的出发点
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+sq[i][j];
ans=max(max(f[m][mid-1],f[m][mid]),f[m][mid+1]);
//很简单 由题意直接可推得 即max(前，左前，右前)
printf("%d\n",ans);
return 0;
}
```
## 十、乌龟棋 ##
[原址](https://www.luogu.org/problemnew/show/P1541)
### 思路 ###
~~**几乎都是这种思路 但好像有人想到了三维的写法**~~
**物品占的空间为1，价值为le[tot]的多重背包**
根据多维背包的思想 当然是 有几种牌就设置几维啊
那么 则有：
1. f[a][b][c][d]:表示你出了a张爬行牌1，b张爬行牌2，c张爬行牌3，d张爬行牌4时的得分
2. le[x]:表示牌x一共有多少张
然后就是用或不用啦 从上一个推来 当然你还要保证 首先你要有这种牌
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=50;
int n,m;
int a[500];
int f[N][N][N][N];
int le[10];
int l1,l2,l3,l4;
int lll;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
scanf("%d",&lll);
le[lll]++;
}
f[0][0][0][0]=a[1];
for(l1=0;l1<=le[1];l1++){
for(l2=0;l2<=le[2];l2++){
for(l3=0;l3<=le[3];l3++){
for(l4=0;l4<=le[4];l4++){
int tot=l1+l2*2+l3*3+l4*4+1;
if(l1) f[l1][l2][l3][l4]=max(f[l1][l2][l3][l4],f[l1-1][l2][l3][l4]+a[tot]);
if(l2) f[l1][l2][l3][l4]=max(f[l1][l2][l3][l4],f[l1][l2-1][l3][l4]+a[tot]);
if(l3) f[l1][l2][l3][l4]=max(f[l1][l2][l3][l4],f[l1][l2][l3-1][l4]+a[tot]);
if(l4) f[l1][l2][l3][l4]=max(f[l1][l2][l3][l4],f[l1][l2][l3][l4-1]+a[tot]);
}
}
}
}
printf("%d\n",f[le[1]][le[2]][le[3]][le[4]]);
return 0;
}
```
## 十一、最大约数和
### 一道水题 ###
[原址](https://www.luogu.org/problemnew/show/P1734)
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e3+500;
int n,f[N],w[N],v[N];//n,存第i个的约数和，容量，约数和
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
w[i]=i;
for(int j=1;j<i;j++)
if(!(i%j))v[i]+=j;
}//预处理 容量和约数和
for(int i=1;i<=n;i++)
for(int j=w[i];j<=n;j++)
f[j]=max(f[j],f[j-w[i]]+v[i]);//状转方程
printf("%d\n",f[n]);
return 0;
}
```
## 十二、创意吃鱼法 ##
[原址](https://www.luogu.org/problemnew/show/P1736)
类似于 **最大正方形** 和 **传纸条**
最大正方形+预处理
传纸条 呃 ~~只是看着像~~
### 思路 ###
- 直接看代码吧 还是比较清晰的
- f[i][j]表示以（i，j）为右下（左下）角的最大对角线长度
>方程：**f[i][j]=min(f[i-1][j-1],min(b[i][j-1],b2[i-1][j]))+1;**
- b[i][j]表示（i，j）最多向左（或右）延伸多少个格子，使这些格子中的数都是0（不包括（i，j））
- b2[i][j]表示（i，j）最多向上延伸多少个格子，使这些格子中的数都是0（不包括（i，j））
b也就是blank啦！
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2600;
int n,m;
int p[N][N];
int b[N][N],b2[N][N];
int f[N][N],ans;
int i,j;
inline void init(){
memset(f,0,sizeof(f));
memset(b,0,sizeof(b));
memset(b2,0,sizeof(b2));
}//注意搜过一次后 要清空数组
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&p[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){//左上——右下
if(!p[i][j]){
b[i][j]=b[i][j-1]+1;
b2[i][j]=b2[i-1][j]+1;
}
if(p[i][j])
f[i][j]=min(f[i-1][j-1],min(b[i][j-1],b2[i-1][j]))+1;
ans=max(f[i][j],ans);
}
init();
for(i=1;i<=n;i++){
for(j=m;j>=1;j--){//右上——左下
if(!p[i][j]){
b[i][j]=b[i][j+1]+1;
b2[i][j]=b2[i-1][j]+1;
}
if(p[i][j])
f[i][j]=min(f[i-1][j+1],min(b[i][j+1],b2[i-1][j]))+1;
ans=max(f[i][j],ans);
}
}
printf("%d\n",ans);
return 0;
}
```
## 十三、导弹拦截
[原址](https://www.luogu.org/problemnew/show/P1020)
### 思路 ###
1. 最长不升子序列
2. 最长上升子序列
二分查找的写法 可以达到O（nlogn）200分
#### 提醒：二分注意边界
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
const int maxn=1e5+50;
const int inf=0x5ffff;
using namespace std;
int k,ans1,ans2;
int h[maxn],a[maxn];
int f[maxn];
int main(){
int n=0;
int l,r,mid;
while(scanf("%d",&a[++n])!=EOF)continue;
n--;
//第一问！！
f[0]=inf;
for(int i=1;i<=n;i++){
if(f[ans1]>=a[i]){
f[ans1+1]=a[i];
ans1++;
}else{
l=0;
r=ans1;
while(l<r){
mid=(l+r)/2;
if(f[mid]>=a[i]){
l=mid+1;
}else{
r=mid;
}
}
if(l!=0)f[l]=a[i];
}
}
printf("%d\n",ans1);
//第二问！！
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++){
if(f[ans2]<a[i]){
f[ans2+1]=a[i];
ans2++;
}else{
l=0;
r=ans2;
while(l<r){
mid=(l+r)/2;
if(f[mid]>=a[i]){
r=mid;
}else{
l=mid+1;
}
}
f[l]=a[i];
}
}
printf("%d\n",ans2);
return 0;
}
```
## 十四、采药
[原址](https://www.luogu.org/problemnew/show/P1048)
水题
01背包
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int T,m;
int t[105],w[105],f[105][1005];
int main(){
scanf("%d%d",&T,&m);
for(int i=1;i<=m;i++)scanf("%d%d",&t[i],&w[i]);
for(int i=1;i<=m;i++){
for(int j=0;j<=T;j++){
f[i][j]=f[i-1][j];
if(j>=t[i]){
f[i][j]=max(f[i][j],f[i-1][j-t[i]]+w[i]);
}
}
}
printf("%d",f[m][T]);
return 0;
}
```
## 十五、疯狂的采药
完全背包
```cpp
#include<cstdio>
#include<cstring>
#include<string>
#define ll long long
using namespace std;
const int maxn=1e6+5;
ll m,n;
ll f[maxn],h[maxn],v[maxn];
inline ll max(ll a,ll b){
if(a>b)return a;
else return b;
}
int main(){
ll i,j;
memset(f,0,sizeof(f));
scanf("%lld%lld",&m,&n);
for(i=1;i<=n;i++)scanf("%lld%lld",&h[i],&v[i]);
for(i=1;i<=n;i++){
for(j=h[i];j<=m;j++){
f[j]=max(f[j],f[j-h[i]]+v[i]);
}
}
printf("%lld",f[m]);
return 0;
}
```
## 十六、开心的金明
[原址](https://www.luogu.org/problemnew/show/P1060)
01背包
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=1e6;
int f[maxn],m[maxn],t[maxn];
int v,n;
int main(){
int w;
scanf("%d%d",&v,&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&t[i],&w);
m[i]=t[i]*w;
}
for(int i=1;i<=n;i++){
for(int j=v-t[i];j>=0;j--){
f[j+t[i]]=max(f[j+t[i]],f[j]+m[i]);
}
}
printf("%d",f[v]);
return 0;
}
```
## 十七、金明的预算方案
[原址](https://www.luogu.org/problemnew/show/P1064)
### 思路
#### 依赖背包
#### 分组背包+01背包
由于有依赖关系 因此可将其抽象为一种**链式结构**
链式结构的思想还是很有趣的
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=4e4;
int n,m;
int s[maxn],t[maxn];
struct bag{
int w,v,zu;
}a[maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i].w,&a[i].v,&a[i].zu);
a[i].v*=a[i].w;//因为要的是乘积最大啊 预处理
}
for(int i=1;i<=m;i++){
if(a[i].zu==0){
//t数组存储选择这一链后所可以取到的最大值
for(int j=1;j<=a[i].w;j++)t[j]=0;//防止等会儿进行分组背包时出现玄学错误
for(int j=a[i].w;j<=n;j++)t[j]=s[j-a[i].w]+a[i].v;// 先全选
for(int j=1;j<=m;j++){
if(a[j].zu==i){
for(int k=n;k>=a[i].w+a[j].w;k--){
t[k]=max(t[k],t[k-a[j].w]+a[j].v);
}
}n
}//有点类似于链式结构 如此遍历一下 再跑一个01背包结束！
for(int j=a[i].w;j<=n;j++){
s[j]=max(t[j],s[j]);
}//取得最大值 其实就是比较而已
}
}
printf("%d\n",s[n]);
return 0;
}
```
## 十八、石子合并
[原址](https://www.luogu.org/problemnew/show/P1880)
### 思路
**区间动规**
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e3;
const int inf=0x7fffffff;
int n;
int a[maxn],w[maxn];//w存前缀和
int f1[maxn][maxn],f2[maxn][maxn];//f1存最小值，f2存最大值
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[n+i]=a[i];//化环为链
}
for(int i=1;i<=2*n;i++){
w[i]=a[i]+w[i-1];//前缀和
}
for(int len=2;len<=n;len++){
for(int i=1;i<=2*n-len+1;i++){//i是合并段开头
int mn=inf,mx=0,j=i+len-1;//mn最小值，mx最大值 ，j是合并段结尾
for(int k=i;k<j;k++){
mn=min(mn,f1[i][k]+f1[k+1][j]+w[j]-w[i-1]);
mx=max(mx,f2[i][k]+f2[k+1][j]+w[j]-w[i-1]);
}
f1[i][j]=mn;
f2[i][j]=mx;//填表
}
}
int mx=0,mn=inf;
for(int i=1;i<=n;i++){
mn=min(mn,f1[i][i+n-1]);
mx=max(mx,f2[i][i+n-1]);
}// 由于为环状，所以需要搜索所有可能满足条件的长度为n的段啊
printf("%d\n%d",mn,mx);
return 0;
}
```
据说有**四边形不等式**优化
#### 此处插旗待拔
这里先附上大佬的讲解 等自己看懂了再写一下
[膜拜神佬.orz](https://www.luogu.org/blog/Hurricane-zjz/solution-p1880)
## 十九、能量项链
[原址](https://www.luogu.org/problemnew/show/P1063)
### 思路
#### 区间动规
```cpp
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int N=250;
int n;
int e[N],f[N][N];//e能量 f动规数组
int main(){
int ans=-1;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&e[i]);
e[i+n]=e[i];//环化链
}
for(int i=2;i<2*n;i++){//1.因为要和前一个珠子合并 因此从2开始循环；
//2.由于环化链的操作 因此到2*n结束
for(int j=i-1;i-j<n&&j>=1;j--){// 从j开始由右向左拓展
for(int k=j;k<i;k++){//中间指针遍历
f[j][i] = max( f[j][i] , f[j][k] + f[k+1][i] + (e[j]*e[k+1]*e[i+1]) );
//动转方程：max（原能量，左区间能量+右区间能量+合并后生成能量）
if(f[j][i]>ans)ans=f[j][i];
}
}
}//区间动规 i右区间边界 j左区间边界 k区间中间指针
printf("%d\n",ans);
return 0;
}
```
其实区间动规的题 就是不断缩小区间 在区间中搜索
## 二十、挖地雷
[原址](https://www.luogu.org/problemnew/show/P2196)
有一定顺序的dp
这道题有很多种做法
树形dp，最长路，dp...
其实只是按照某种特殊顺序关系进行转移，即**连接性**
其实是数字三角形加强版，当然 由于这种特殊的结构，就会有人想到树形dp啦
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
int n,ans;
int a[400],f[400],ne[400];
bool t[400][400];
using namespace std;
int main(){
int k;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
scanf("%d",&k);
if(k==1)t[i][j]=true;
else t[i][j]=false;//记录是否联通
}
for(int i=n-1;i>=1;i--){
f[n]=a[n];
for(int j=i+1;j<=n;j++)
if(f[j]>f[i]&&t[i][j]){
f[i]=f[j];
ne[i]=j;
}//在i之后的区域里找到最大的总和且连通的地窖，把i的连接的地窖设为最大的
f[i]+=a[i];
}
for(int i=1;i<=n;i++)
if(f[i]>ans){
ans=f[i];
k=i;
}//存最优
int i;
for(i=k;ne[i];i=ne[i])
printf("%d ",i);
printf("%d\n",i);
printf("%d\n",ans);
return 0;
}
```
## 二十一、巨大的牛棚Big Barn
[原址](https://www.luogu.org/problemnew/show/P2701)
#### 最大子矩阵 诶前文好像有创意吃鱼法
**它俩炒鸡像的QAQ**
直接看代码好不好
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>//最大子矩阵QAQ
using namespace std;
const int maxn=1050;
int n,t;
int d[maxn][maxn],a,b;
int f[maxn][maxn];
int ans;
int main(){
scanf("%d%d",&n,&t);
for(int i=1;i<=t;i++){
scanf("%d%d",&a,&b);
d[a][b]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!d[i][j]){
f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;//状转方程
ans=max(ans,f[i][j]);//取最大值
}
printf("%d\n",ans);
return 0;
}
```
## 二十二、过河
不是那道很水的过河啦！
[原址](https://www.luogu.org/problemnew/show/P1052)
### 思路
#### 离散化+dp
难度适中 请看代码
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int N=500;
const int M=2e4+500;
int l;
int s,t,m;
int stone[N];//石子路
int f[M],vis[M];//f:走到当前长度所踩到的最少石子数
int len;//石子路长度
inline void pre(){
stone[m+1]=l;//要把终点加入 也当作一个无石头的石头
sort(stone,stone+m+2);//输入没有保证有序哦
for(int i=1;i<=m+1;i++){
if(stone[i]-stone[i-1]>=t)len+=(stone[i]-stone[i-1])%t+t;//%t+t是个好习惯
else len+=stone[i]-stone[i-1];
/*分析题目可以发现 两点间的距离dis大于t时，
一定可以由d%t跳过来，所以最多只需要dis%t+t种距离的状态就可以表示这两个石子之间的任意距离关系
*/
vis[len]=1;//表示这里有石头
}
vis[len]=0;//表示这里没有石头 走起来比较优
}//其实这步是进行了一步离散化
int main(){
scanf("%d",&l);
scanf("%d%d%d",&s,&t,&m);
for(int i=1;i<=m;i++)scanf("%d",&stone[i]);
pre();
memset(f,0x3f,sizeof(f));f[0]=0;
for(int i=1;i<=len+t-1;i++)/*因为终点可以正好跳到 也可以直接跳过去所以并不是一个确切的点
而是一个范围 因此总路径长需要+t(最后一步最远长度)-1*/
for(int j=s;j<=t;j++)
if(i-j>=0)f[i]=min(f[i],f[i-j]+vis[i]);//方程贼简单 不解释
int ans=0x7ffffff;//先赋个极大值
for(int i=len;i<=len+t-1;i++)/*因为终点可以正好跳到 也可以直接跳过去所以并不是一个确切的点
而是一个范围 所以需要在这个区间内找到一个最小值*/
ans=min(f[i],ans);
printf("%d\n",ans);
return 0;
}
```
## 二十三、小a和uim之大逃离
[原址](https://www.luogu.org/problemnew/show/P1373)
由于洛谷原创 因此题目很有意思QAQ
>
**nm的巨幅矩阵**，矩阵的每个格子上有一坨**0~k不等量
**的魔液。怪物各给了小a和uim一个魔瓶，说道，你们可以从矩阵的**任一个格子开始**，**每次向右或向下走一步，从任一个格子结束**。开始时小a用魔瓶吸收地面上的魔液，下一步由uim吸收，如此**交替**下去，并且要求**最后一步必须由uim吸收**。魔瓶只有**k的容量**，也就是说，如果**装了k+1那么魔瓶会被清空成零**，如果装了k+2就只剩下1，依次类推。怪物还说道，最后谁的魔瓶装的魔液多，谁就能活下来。小a和uim感情深厚，情同手足，怎能忍心让小伙伴离自己而去呢？沉默片刻，小a灵机一动，如果他俩的魔瓶中**魔液一样多**，不就都能活下来了吗？小a和他的小伙伴都笑呆了！
现在他想知道他们都能活下来**有多少种方法**。
### 思路
路径行走类问题
1. 既然他们要求瓶内魔液一样多 那就让他们一起走
2. 那么现在问题来了 如何消除后效性？
当然是 再加一维啦 存当到达这个点时 两者瓶内魔液差值
3. 注意这个差值需要枚举啦 因为首先他是让你统计方案数啊
4. 具体转移过程：
```cpp
f[i][j][d][0]=(f[i][j][d][0]+f[i-1][j][(d-a[i][j]+k)%k][1])%mo;//小a取 差值减小 +k是防止搞成负数
f[i][j][d][0]=(f[i][j][d][0]+f[i][j-1][(d-a[i][j]+k)%k][1])%mo;
f[i][j][d][1]=(f[i][j][d][1]+f[i-1][j][(d+a[i][j])%k][0])%mo;//uim再取 差值就会变大
f[i][j][d][1]=(f[i][j][d][1]+f[i][j-1][(d+a[i][j])%k][0])%mo;
```
那么 code：
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int mo=1e9+7;
int n,m,k;
int a[840][840];
int f[840][840][18][2];
//i,j:(i,j),d:差值,w:a||uim
ll ans;
int main(){
scanf("%d%d%d",&n,&m,&k);
k=k+1;//其实按照题意 k就是一个模数 但是要模k+1 因为当装到k时不会清零 k+1才会
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
f[i][j][a[i][j]%k][0]=1;//小a先走 这一步表示 小a可以从任一个点出发
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int d=0;d<=k;d++){
f[i][j][d][0]=(f[i][j][d][0]+f[i-1][j][(d-a[i][j]+k)%k][1])%mo;
f[i][j][d][0]=(f[i][j][d][0]+f[i][j-1][(d-a[i][j]+k)%k][1])%mo;
f[i][j][d][1]=(f[i][j][d][1]+f[i-1][j][(d+a[i][j])%k][0])%mo;
f[i][j][d][1]=(f[i][j][d][1]+f[i][j-1][(d+a[i][j])%k][0])%mo;
}
ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=(ll)(f[i][j][0][1]+ans)%mo;//因为是uim走最后一步 所以这里用他来讨论答案
printf("%lld\n",ans);
return 0;
}
```
但是这个题 最坑的在于：
# 卡空间
毒瘤啊啊啊啊啊！！！我一点点卡过的啊啊啊
~~其实思路也不算很难~~
## 关路灯
[原址](https://www.luogu.org/problemnew/show/P1220)
### 思路
不难 蛮简单
#### 类似于区间动规
题解中 有一个讲的极好的:
@z2415445508
关灯不需要额外的时间，经过了灯就关了。但是可能折返回去关某一个大灯会比继续往下走关接下来的一个小灯更优，
那么可以得到两种状态（沿着当前方向继续往下走，改变方向回去关灯）。
我们需要得到的整个关灯过程中的最优值（最小耗能）
那么要设计的状态转移方程中肯定有两种方案（折返的，不撞墙不回头的）
又因为如果想要关某一区间的灯的过程中耗能最小，所以可以转换成一个个区间来写：
去关某一区间的灯，那么整条街道上除了这一区间的灯会逐渐灭掉其他肯定会全亮。
那么我们把f[i][j]记为当从i到j的灯都熄灭后剩下的灯的总功率。
再进一步：f[i][j][0]表示关掉i到j的灯后，老张站在i端点，f[i][j][1]表示关掉[i][j]的灯后,老张站在右端点
（i为左端点，j为右端点）
又f[i][j][0]会由两种方案推导而来（上面有写。）：折返回来关i,j的灯、由i+1深入，继续关第i盏灯从而扩展到（i,j）；
所以得到状态转移方程：
>**f[i][j][0] = min ( f[i+1][j][0] + ( a[i+1] - a[i] ) * ( sum[i] + sum[n] - sum[j] ) , f[i+1][j][1] + ( a[j]-a[i] ) * ( sum[i]+sum[n]-sum[j]) );**
>**f[i][j][1] = min ( f[i][j-1][0] + ( a[j] - a[i] ) * ( sum[i-1] + sum[n] - sum[j-1] ) , f[i][j-1][1] + ( a[j]-a[j-1] ) * ( sum[i-1] + sum[n] - sum[j-1] ) );**
（枚举现在的路灯l（2-n,因为第c位的路灯已经被关了），i+l-1<=n（路只有这么长），j=i+l-1（右端点））
因为最后不知道老张到底站在左端点最优还是站在右端点最优
所以在f[1][n][0]和f[1][n][1]中取min输出。
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100;
int n,c;
int id[N],p[N];
int sum[N];
int f[N][N][3];
int ans;
int main(){
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++){
scanf("%d%d",&id[i],&p[i]);
sum[i]=sum[i-1]+p[i];
}
memset(f,0x3f,sizeof(f));
f[c][c][0]=0;f[c][c][1]=0;
for(int l=2;l<=n;l++){
for(int i=1;i+l-1<=n;i++){
int j=i+l-1;
f[i][j][0]=min(f[i+1][j][0]+(id[i+1]-id[i])*(sum[i]+sum[n]-sum[j]),
f[i+1][j][1]+(id[j]-id[i])*(sum[i]+sum[n]-sum[j]));
f[i][j][1]=min(f[i][j-1][0]+(id[j]-id[i])*(sum[i-1]+sum[n]-sum[j-1]),
f[i][j-1][1]+(id[j]-id[j-1])*(sum[i-1]+sum[n]-sum[j-1]));
}
}
ans=min(f[1][n][0],f[1][n][1]);
printf("%d\n",ans);
return 0;
}
```
1.[教你彻底学会动态规划——入门篇](http://blog.csdn.net/baidu_28312631/article/details/47418773)
2.[白话算法之动态规划](http://blog.csdn.net/u013445530/article/details/45645307)