《紫书：动态规划初步》总结一

动态规划初步》总结一"/>

《紫书：动态规划初步》总结一

数字三角形问题：

每个单独的点基本都是有两个父亲，有两个孩子。

我们在贪心计算的时候，走错了孩子会导致局部最优而不是全局最优。

因为我们舍弃了一些情况，暴力枚举不会舍弃任何情况，但是会导致重复枚举。因为左父亲要走这个孩子，右父亲也是。

考虑动态规划：

每个点走到最后一层的最大值是不受上层结构的影响的。(无后效性)

如果从根节点开始走，走到i点是最好的选择，那么一定包含剩下的i点的最优路径。(全局最优解包含局部最优解，最优子结构性质)

DAG模型

这里有两个问题：嵌套矩形问题和硬币问题。

如果嵌套关系满足，建立一条有向边。

如果要满足S，那么S->S-V[i]就是一条有向边，不过做这道题实际不用建边。

dp[i]=max(dp[j]+1)；dp[i]表示从i出发的最长路长度。

如果要求字典序输出的话：print_ans(i){}每次递归遍历一遍n，满足转移方程的说明是一条可行路径，直接继续打印即可。

不过要提前选好dp[i]最大。

最后总结：

不过这里涉及到的都是填表法，对于每个状态，找到f[i]依赖的所有状态。

有时候更方便的是，对于每个状态i,更新f[i]影响的所有状态(刷表法)

拓扑排序枚举i，对于每个i，枚举(i,j)，更新dp[j]。PS：不过前提是，依赖的这些状态相互独立地影响，不需要和在一起什么的。

练习

A Spy in the Metro:UVA - 1025

题意：某个人在第一个站，需要在时间T会见在第n个站的一个人。

站是线性的，告诉你从左边第一个往右的M1列车的发车时间，从右边第一个往左的M2列车的发车时间。

同时不同列车在某两个站之间开的时间是固定的。

我们要求在车站的最小等待时间(每个车必定会在站里停，不过时间很短。在这个时间里你可以换乘反方向的车，时间很短忽略不计)。

假设我们在第i个站，这时候我们可以停一分钟，或者坐向左的车，或者坐向右的车。(如果原本就是向左的，那相当于没有变)

所以我们不考虑是等了几分钟的还是刚刚开到，这样可以减少状态数。

同时我们要判断有没有这个车，必须记录时间。这样子就可以判断决策是否可以执行了。

决策有三个，是上面的红色部分。

边界条件就是：在T时刻如果在第N个站，就可以直接会面了dp[T][N]=0。

所以这里我们需要从后往前递推。用has_train判断有没有车。

无后效性：假如我到第i个站花了最小T时间，第i个站到最后一个站花了最小t时间，两者不可能影响。

最优子结构：保证全局最小，第i个站到最后一个站肯定是最小的。

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;#define ll long long
#define M 400010
#define inf 0x3f3f3f3fint N,T,M1,M2;
int t[M],now;
int has_train[505][505][2];
int dp[505][505];
//dp[i][j],when time is at "i",we are at the j-th station,we need to wait how long?
int main(){int cnt=0;while(cin>>N){if(N==0)break;scanf("%d",&T);t[0]=0;t[N]=0;FOR(i,1,N-1)scanf("%d",&t[i]);memset(dp,0,sizeof(dp));memset(has_train,0,sizeof(has_train));scanf("%d",&M1);FOR(i,1,M1){scanf("%d",&now);FOR(j,1,N){now+=t[j-1];has_train[now][j][1]=1;//right}}scanf("%d",&M2);FOR(i,1,M2){scanf("%d",&now);FOR(j,1,N){now+=t[N-j+1];has_train[now][N-j+1][0]=1;//left}}FOR(i,1,N-1)dp[T][i]=inf;dp[T][N]=0;for(int i=T-1;i>=0;i--)for(int j=1;j<=N;j++){dp[i][j]=dp[i+1][j]+1;if(j>1&&has_train[i][j][0]&&i+t[j-1]<=T)dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);if(j<N&&has_train[i][j][1]&&i+t[j]<=T){dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);}//cout<<dp[i][j]<<":"<<i<<" "<<j<<endl;}if(dp[0][1]>=inf)printf("Case Number %d: impossible\n",++cnt);else{printf("Case Number %d: %d\n",++cnt,dp[0][1]);}}
}

The Tower of Babylon:UVA - 437 

题意：有n种长方体，你可以把一个面作为底面，每种长方体有无限种。

需要造一个塔，把一个面作为底面放已经组成的塔的顶部。[但是加入的底面要比顶部的低]

问最高高度。

:::这是一道变相的嵌套矩阵题目，每个长方体取长宽高的一个作为塔上的高，可以组成三种底面。

:::那么一种是3*n的状态，每个状态对其他的状态如果有嵌套关系，我们就建立有向边。

最后进行记忆化搜索，3*n*3*n=>9n^2

那么状态记录就是第i个长方体，j表示0、1、2，取第几个为塔上的高度。

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;#define ll long long
#define M 400010
#define inf 0x3f3f3f3fint n;
int A[303][3];
int dp[303][3];//dp[i][j] when i-th block is the top,and j-th is its height,then we get the maximum height;vector<pair<int,int> >G[303][3];int check(int i,int j,int k1,int k2){int mini=inf,minj=inf,maxi=-1,maxj=-1;FOR(k,0,2)if(k!=k1){mini=min(mini,A[i][k]);maxi=max(maxi,A[i][k]);}FOR(k,0,2)if(k!=k2){minj=min(minj,A[j][k]);maxj=max(maxj,A[j][k]);}return mini<minj&&maxi<maxj;
}int DP(int i,int k){if(dp[i][k]!=-1)return dp[i][k];for(int j=0;j<G[i][k].size();j++){int x=G[i][k][j].first,y=G[i][k][j].second;dp[i][k]=max(dp[i][k],(dp[x][y]=DP(x,y))+A[i][k]);}if(dp[i][k]<A[i][k])dp[i][k]=A[i][k];//cout<<i<<" "<<k<<" "<<dp[i][k]<<endl;return dp[i][k];
}int main(){int cnt=0;while(cin>>n){if(n==0)break;memset(dp,-1,sizeof(dp));FOR(i,1,n)FOR(k,0,2)G[i][k].clear();FOR(i,1,n){scanf("%d%d%d",&A[i][0],&A[i][1],&A[i][2]);sort(A[i],A[i]+3);}FOR(i,1,n)FOR(k1,0,2)FOR(j,1,n)FOR(k2,0,2){if(check(i,j,k1,k2))G[i][k1].push_back(make_pair(j,k2));}FOR(i,1,n)FOR(k,0,2)DP(i,k);int ans=-1;for(int i=1;i<=n;i++)for(int k=0;k<3;k++)ans=max(ans,dp[i][k]);printf("Case %d: maximum height = %d\n",++cnt,ans);}
}

Tour:UVA - 1347 

题意：从第1个点经过中间点到第n个点，再经过中间点回到第一点，贡献为两点间距离。同时中间点必须也只能遍历一次。

对这道题的理解可能还是不太够，现在只放上目前的理解。

考虑动态规划：我们可以把问题转换成两个人从1~n，中间路径不能重合。保证路径不能重合的状态是比较难的，所以我们考虑使用f[i][j]表示走遍了1~max(i,j)的距离，这样就能保证不会走以前的点。同时f[i][j]表示的是走到这个状态还要走多少路。(因为这样可以方便维护最后边界状态，已经走到n-1了)

同样的，f[i][j]=f[j][i].所以我们人为规定i>j,方便做题。

走到i和j了之后，i可以走到i+1,i+2,...,n，但是由于走的状态是一路向前的，i走了i+2,就得j走i+1。

所以我们只考虑谁走了i+1来写状态转移方程：dp[i][j]=max(dp[i+1][j]+cal(i,i+1),dp[i+1][i]+cal(j,i+1)).

决策只有两种，状态的话是n^2.，边界状态dp[n-1][i]=dist(n-1,n)+dist(i,n);

答案是dp[2][1]+dist(1,2)因为规定i>j，所以要这么写。

【这是目前的理解：对于不能重复的dp，状态是比较难以维护的，我们可以用前缀都已经遍历的状态来实现简单的维护】

memset对double数组0x43是较大值，0xc2是较小值。

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;#define ll long long
#define M 5010
#define inf 0x3f3f3f3fstruct node{double x,y;void inp(){scanf("%lf%lf",&x,&y);}
}A[M];int n;
double dp[M][M];double cal(node a,node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}int main(){while(cin>>n){FOR(i,1,n)A[i].inp();memset(dp,0x43,sizeof(dp));//记录一下double数组的情况FOR(i,1,n-2)dp[n-1][i]=cal(A[i],A[n])+cal(A[n-1],A[n]);for(int i=n-2;i>=1;i--)//dp[i][j]=(dp[i+1][j],dp[i+1][i])for(int j=1;j<i;j++)dp[i][j]=min(dp[i+1][j]+cal(A[i],A[i+1]),dp[i+1][i]+cal(A[j],A[i+1]));double ans=dp[2][1]+cal(A[1],A[2]);//to get dp[2][1]printf("%.2lf\n",ans);}
}