UVA_1025 a Spy in the Metro 有向无环图的动态规划问题
2024-09-04 00:12:28
应当认为,有向无环图上的动态规划问题是动态规划的基本模型之一,对于某个模型,如果可以转换为某一有向无环图的最长、最短路径问题,则可以套用动态规划若干方法解决。
原题参见刘汝佳紫薯267页。
在这个题目中,首先将整个模型规划成为有向无环图的模式:
1,对于某小特工,于j时间处在在第i站,可以成为一个独立的状态,也就是有向无环图的一个节点。
2,对于每个节点,可能能够走得有三个不同的边——坐火车往左走,进入左边的某个状态;坐火车往右走,进入右边的某个状态;原地等待,进入该站点的下一个时间。
每条边,拥有权重——坐火车边权位0,但是原地等待边权位1.,由此,可以将动态规划的问题描述成为一个有向无环图上的寻路问题。直觉上至少可以使用最短路算法。
但是对于有向无环图情况,可以进行特殊的优化:使用直接刷表法求得。
之前,我们大多使用“对于每个节点进行扫描的时候更新该节点的所有子节点中某值,从而使得,该节点得到最优解”。但是很多时候,并不一定可以使用这种思路来进行很直观的赋值。在这种情况下,我们可以退而求其次,通过若干次计算,在到达某一节点之后“更新”可能直接到达的节点的边权,从而得到,我们需要的最值。
这道题在做的时候,感觉到有些比较深的坑——例如初始化的故事。
AC代码:
#include<bits/stdc++.h>
using namespace std; const long long MAXN=;
const long long INF=1e9+;
long long n,t,m1,m2;
long long ti[MAXN];
long long d1[MAXN];
long long d2[MAXN];
bool check[MAXN][MAXN][];
long long dp[MAXN][MAXN]; long long ca=;
void init()
{
memset(check,,sizeof(check));
memset(ti,,sizeof(ti));
memset(d1,,sizeof(d1));
memset(d2,,sizeof(d2));
cin>>t;
for(int i=;i<n-;++i) cin>>ti[i];
cin>>m1;
for(int i=;i<m1;++i) cin>>d1[i];
cin>>m2;
for(int i=;i<m2;++i) cin>>d2[i];
check[][d1[]][]=;check[n-][d2[]][]=; for(int i=;i<MAXN;++i)
{
for(int j=;j<MAXN;++j)dp[i][j]=INF;
}long long time=;
for(int i=;i<n-;++i)
{ for(int j=;j<m1;++j)
{
check[i][d1[j]+time][]=;
// cout<<"left: "<<i<<ends<<d1[j]+time<<endl;
}time+=ti[i];
}
time=;
for(int i=n-;i;--i)
{
time+=ti[i];
for(int j=;j<m2;++j)
{
check[i][d2[j]+time][]=;
// cout<<"right: "<<i<<ends<<d2[j]+time<<endl;
}
}dp[][]=;
for(int j=;j<=t;++j)
{
for(int i=;i<n;++i)
{
if(dp[i][j]>=INF)continue;
dp[i][j+]=min(dp[i][j]+,dp[i][j+]);
if(i<n-&&check[i][j][])dp[i+][j+ti[i]]=min(dp[i][j],dp[i+][j+ti[i]]);//,cout<<"check_left "<<i<<ends<<j<<ends<<dp[i][j]<<endl;
if(i&&check[i][j][])dp[i-][j+ti[i-]]=min(dp[i][j],dp[i-][j+ti[i-]]);//,cout<<"check_right "<<i<<ends<<j<<ends<<dp[i][j]<<endl;
}
}
cout<<"Case Number "<<ca++<<": ";
if(dp[n-][t]<INF)cout<<dp[n-][t]<<"\n";
else cout<<"impossible\n"; } int main()
{
cin.sync_with_stdio(false);
while(cin>>n&&n)init(); return ;
}
最新文章
- Sass学习笔记
- 关于MySQL存储过程中遇到的一个错误
- JackRabbit的前世今生
- easyui 使用问题积累
- github page 构建自己的页面
- win7下搭建PHP环境
- Bridge 模式
- linux串口驱动分析——发送数据
- javascript中this、apply、call、bind的用法和区别
- MVC View显示详解(RenderBody,RenderPage,RenderSection,Partial)
- 初次真正意义上的接触Eclipse
- pwn学习日记Day1 基础知识积累
- leetcode 二进制求和 python
- Uncaught TypeError: form.attr is not a function 解决办法
- Python学习笔记 -- 第六章 文件操作
- HDU 1024 Max Sum Plus Plus (动态规划)
- jquery ajax的load()方法和load()事件
- error: libXpm.(a|so)
- hdoj 5119 Happy Matt Friends 背包DP
- MySQl安装全解