首页 > 代码库 > DAG上的动态规划
DAG上的动态规划
UVA1025
分析:因为时间是单向流逝的,是天然的"序",所以影响决策的只有当前时间和所处的决策。dp[i][j],表示在第i分钟时,处于第j个车站,最少还需要多少等待时间,因此其等待时间就有站原地等待,乘坐从左到右的车,乘坐从右到左的车,三个状态来决定。
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "string" 5 using namespace std; 6 const int maxn=1000+100; 7 const int maxm=10000+100; 8 const int INF=1<<30; 9 int n,T,m1,m2; 10 int t[maxn],d[maxn],e[maxn]; 11 int dp[maxm][60],vis[maxm][60][3]; 12 int main() 13 { 14 int cas=0; 15 while(cin>>n) 16 { 17 if(n==0) break; 18 cin>>T; 19 memset(vis,0,sizeof(vis)); 20 memset(dp,0,sizeof(dp)); 21 memset(t,0,sizeof(t)); 22 for(int i=1;i<n;i++) 23 cin>>t[i]; 24 cin>>m1; 25 for(int i=1;i<=m1;i++) 26 cin>>d[i]; 27 cin>>m2; 28 for(int i=1;i<=m2;i++) 29 cin>>e[i]; 30 //从左到右 31 for(int i=1;i<=m1;i++){ 32 int cnt=d[i]; 33 for(int j=1;j<=n;j++){ 34 vis[cnt][j][0]=1; 35 cnt+=t[j]; 36 } 37 } 38 //从右到左 39 for(int i=1;i<=m2;i++){ 40 int res=e[i]; 41 for(int j=n;j>=1;j--){ 42 vis[res][j][1]=1; 43 res+=t[j-1]; 44 } 45 } 46 47 for(int i=1;i<n;i++) dp[T][i]=INF; 48 dp[T][n]=0; 49 for(int i=T-1;i>=0;i--){ 50 for(int j=1;j<=n;j++){ 51 dp[i][j]=dp[i+1][j]+1; 52 if(j<n&&vis[i][j][0]&&(i+t[j]<=T)) //从左到右 53 dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]); 54 if(j>1&&vis[i][j][1]&&(i+t[j-1]<=T)) 55 dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]); 56 } 57 } 58 printf("Case Number %d: ",++cas); 59 if(dp[0][1]>=INF) cout<<"impossible"<<endl; 60 else cout<<dp[0][1]<<endl; 61 62 } 63 return 0; 64 }
DAG上的动态规划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。