DP · 真题
下面是几道CSP/NOIP真题（如题，都是DP）
[NOIP2017 普及组] 棋盘
[NOIP2014 提高组] 飞扬的小鸟
[NOIP2015 提高组] 子串
[NOIP2017 普及组] 跳房子
[NOIP2018 普及组] 摆渡车
（大概按难易程度排了一下吧）.
棋盘
看题像极了DP，但数据范围没有那么大，\(so\) 记忆化搜索似乎能过
用一个数组 \(ans[i][j][dir](0\leq dir<4)\) 表示在 \((i,j)\) 这个节点上，上一步从 \(dir\) 这个方向来的硬币花费最小。（ \(dir\) 具体表示哪个方向并不用在意）.
如果 走到当前这个点的花费 \(\geq ans[x][y][dir]\) 那就不用再搜下去了.
（个人认为这个方法十分的玄学，但它过了）.
放一个 \(dfs\) 的代码吧：
const int Ma=0x3f3f3f3f;
int n,m;
int mp[105][105],ans[105][105][4];
bool v[105][105];
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
void dfs(int xx,int yy,int coin,bool is,int dir){
if(ans[xx][yy][dir]<=coin) return;
ans[xx][yy][dir]=coin;
if(xx==n && yy==n) return;
for(int i=0;i<4;++i){
int x=dx[i]+xx,y=dy[i]+yy;
if(x>0 && x<=n && y>0 && y<=n && !v[x][y]){
v[x][y]=1;
if(mp[x][y]==0){
if(!is)
mp[x][y]=mp[xx][yy],dfs(x,y,coin+2,1,i),mp[x][y]=0;
}
else{
if(mp[x][y]==mp[xx][yy]) dfs(x,y,coin,0,i);
if(mp[x][y]!=mp[xx][yy]) dfs(x,y,coin+1,0,i);
}
v[x][y]=0;
}
}
}
飞扬的小鸟
一看就是DP，但是细节稍稍有亿点点多.
用一个二维数组 \(f[i][j]\) 表示在横坐标为 \(i\) ，高度为 \(j\) 的位置上的最小点击次数.
再用当前这个状态去更新横坐标为 \(i+1\) 的可到达高度的 \(f\) 数组.
一个没有过的（\(T\) 掉了）\(dp\) 核心：
for(int i=0;i=hig[i])){
f[i][j]=Maxn;
continue;
}
if(j-dow[i]>low[i+1] && j-dow[i]<(hig[i+1]==m?m+1:hig[i+1]))
f[i+1][j-dow[i]]=min(f[i+1][j-dow[i]],f[i][j]);
int k;
if(hig[i+1]==m){
int tmp=Maxn;
for(k=1;tmp!=m;++k)
tmp=min(m,j+fl[i]*k),f[i+1][tmp]=min(f[i+1][tmp],f[i][j]+k);
}
else{
for(int k=1;k 子串
用数组 \(f[i][j][k]\) 表示 \(a\) 字符串前 \(i\) 个字符构成的字符串与 \(b\) 字符串前 \(j\) 个字符构成的字符串，划分 \(k\) 次的匹配方案数.
\[f[i][j][k]=f[i-1][j-1][k](a[i]\neq b[j]) \]\[f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k-1](a[i]=b[j],a[i-1]\neq b[j-1]) \]\[... \]\(dp\) 核心：
f[0][0]=1;
for(int i=1;i<=n;++i)
for(int j=m;j>=1;--j)
for(int q=k;q>=1;--q){
sum[j][q]=(a[i-1]==b[j-1]?sum[j-1][q]+f[j-1][q-1]:0)%mod;
f[j][q]=(f[j][q]+sum[j][q])%mod;
}
跳房子
数据范围这么大，就用二分枚举使用的金币个数，最关键的就是 \(check\) 函数了
这肯定就是个DP了 （废话，出现在这篇博客里的不都是吗）
用 \(f[i]\) 表示第跳到第 \(i\) 个点时，最大的分数
\[f[i]=\max_{i-(d+k)\leq j\leq i-max(d-k,1)}(f[j])+f[i] \]直接找最大值有点费时，用一个单调队列优化一下
\(check\) 函数：
bool ch(int q){
int l=max(1ll,d-q),r=d+q;
deque mm;
int j=0;
for(int i=1;i<=n;++i){
while(j=l){
if(!mm.size()) mm.push_back(j);
else{
while(mm.size() && f[j]>=f[mm.back()])
mm.pop_back();
mm.push_back(j);
}
++j;
}
while(mm.size() && x[i]-x[mm.fr]>r) mm.pop_front();
if(mm.size()) f[i]=f[mm.fr]+s[i];
else f[i]=-999999999999;
if(f[i]>=k) return 1;
}
return 0;
}
一定！ 一定！ 记得 define int ll
(否则最后一个点过不去）
摆渡车
这样把他抽象化一下:
令 \(f[i]\) 表示最后一段的右边界为 \(i\) 的方案的最小等车时间.
\[f[i]=\min_{0\leq j\leq i-m}(\sum_{j注意 ：\(i\) 最大要取到 \((\max t[k])+m\)
这样转移的复杂度远大于 \(O(t^2)\) ,这不就 \(TLE\) 了嘛
拆分一下：
\[\sum_{j\(\sum i\) 为 \(j\) 到 \(i-m\) 之间新来的等车人数
\(\sum t_k\) 为这段时间内每一个人的到达时间之和
这两个和都可以用 前缀和 预处理
这样的时间复杂度到了 \(O(t^2)\) ，可惜还是会 \(T\)
当 \(i\leq i-2m\) 时可以跑至少两个来回，这样一定会更优，所以 \(j\) 只需要从 \(i-2m\) 枚举到 \(i-m\),这样就 \(A\) 啦
\(dp\) 核心：
int ans=1e9;
for(int i=m;i<=mt+m;++i){
if(cnt[i]==cnt[i-m]){
f[i]=f[i-m];
continue;
}
for(int j=max(0,i-m*2+1);j<=i-m;++j)
f[i]=min(f[i],f[j]+sum[i]-sum[j]-cnt[j]*(i-j));
}