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

发布于:2021-11-30 17:13:42

数字三角形问题:

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


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


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


考虑动态规划:


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


如果从根节点开始走,走到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,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
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

#define ll long long
#define M 400010
#define inf 0x3f3f3f3f

int 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 dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);
}
//cout< }
if(dp[0][1]>=inf)printf("Case Number %d: impossible
",++cnt);
else{
printf("Case Number %d: %d
",++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
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

#define ll long long
#define M 400010
#define inf 0x3f3f3f3f

int 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 >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}

int DP(int i,int k){
if(dp[i][k]!=-1)return dp[i][k];
for(int j=0;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] //cout< 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
",++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
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

#define ll long long
#define M 5010
#define inf 0x3f3f3f3f

struct 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 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
",ans);
}
}

?

相关推荐

最新更新

猜你喜欢